//===--- Demangle.cpp - Swift Name Demangling -----------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
//  This file implements declaration name demangling in Swift.
//
//===----------------------------------------------------------------------===//

//#include "swift/Basic/Demangle.h"
//#include "swift/Basic/Fallthrough.h"
//#include "swift/Strings.h"
//#include "swift/Basic/LLVM.h"
//#include "swift/Basic/Punycode.h"
//#include "swift/Basic/UUID.h"
//#include "llvm/ADT/StringRef.h"
#include "Demangle.h"
#include "Fallthrough.h"
#include "SwiftStrings.h"
#include "LLVM.h"
#include "Punycode.h"
//#include "UUID.h"
#include "Optional.h"
#include "StringRef.h"
#include <functional>
#include <inttypes.h>
#include <vector>
#include <cstdio>
#include <cstdlib>

using namespace swift;
using namespace Demangle;

[[noreturn]] static void unreachable(const char *Message) {
    fprintf(stderr, "fatal error: %s\n", Message);
    std::abort();
}

DemanglerPrinter &DemanglerPrinter::operator<<(unsigned long long n) & {
    char buffer[32];
    snprintf(buffer, sizeof(buffer), "%" PRIu64, n);
    Stream.append(buffer);
    return *this;
}
DemanglerPrinter &DemanglerPrinter::operator<<(long long n) & {
    char buffer[32];
    snprintf(buffer, sizeof(buffer), "%" PRId64, n);
    Stream.append(buffer);
    return *this;
}

namespace {
struct QuotedString {
    std::string Value;

    explicit QuotedString(std::string aValue) : Value(aValue) {}
};
} // end anonymous namespace.

static DemanglerPrinter &operator<<(DemanglerPrinter &printer, const QuotedString &QS) {
    printer << '"';
    for (auto C : QS.Value) {
        switch (C) {
            case '\\':
                printer << "\\\\";
                break;
            case '\t':
                printer << "\\t";
                break;
            case '\n':
                printer << "\\n";
                break;
            case '\r':
                printer << "\\r";
                break;
            case '"':
                printer << "\\\"";
                break;
            case '\'':
                printer << '\'';
                break; // no need to escape these
            case '\0':
                printer << "\\0";
                break;
            default:
                auto c = static_cast<char>(C);
                // Other ASCII control characters should get escaped.
                if (c < 0x20 || c == 0x7F) {
                    static const char Hexdigit[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
                    printer << "\\x" << Hexdigit[c >> 4] << Hexdigit[c & 0xF];
                } else {
                    printer << c;
                }
                break;
        }
    }
    printer << '"';
    return printer;
}

Node::~Node() {
    switch (NodePayloadKind) {
        case PayloadKind::None:
            return;
        case PayloadKind::Index:
            return;
        case PayloadKind::Text:
            TextPayload.~basic_string();
            return;
    }
    unreachable("bad payload kind");
}

namespace {
struct FindPtr {
    FindPtr(Node *v) : Target(v) {}
    bool operator()(NodePointer sp) const { return sp.get() == Target; }

private:
    Node *Target;
};
} // end anonymous namespace

static bool isStartOfIdentifier(char c) {
    if (c >= '0' && c <= '9')
        return true;
    return c == 'o';
}

static bool isStartOfNominalType(char c) {
    switch (c) {
        case 'C':
        case 'V':
        case 'O':
            return true;
        default:
            return false;
    }
}

static bool isStartOfEntity(char c) {
    switch (c) {
        case 'F':
        case 'I':
        case 'v':
        case 'P':
        case 's':
        case 'Z':
            return true;
        default:
            return isStartOfNominalType(c);
    }
}

static Node::Kind nominalTypeMarkerToNodeKind(char c) {
    if (c == 'C')
        return Node::Kind::Class;
    if (c == 'V')
        return Node::Kind::Structure;
    if (c == 'O')
        return Node::Kind::Enum;
    return Node::Kind::Identifier;
}

static std::string archetypeName(Node::IndexType index, Node::IndexType depth) {
    DemanglerPrinter name;
    do {
        name << (char)('A' + (index % 26));
        index /= 26;
    } while (index);
    if (depth != 0)
        name << depth;
    return std::move(name).str();
}

namespace {

/// A convenient class for parsing characters out of a string.
class NameSource {
    StringRef Text;

public:
    NameSource(StringRef text) : Text(text) {}

    /// Return whether there are at least len characters remaining.
    bool hasAtLeast(size_t len) { return (len <= Text.size()); }

    bool isEmpty() { return Text.empty(); }
    explicit operator bool() { return !isEmpty(); }

    /// Return the next character without claiming it.  Asserts that
    /// there is at least one remaining character.
    char peek() { return Text.front(); }

    /// Claim and return the next character.  Asserts that there is at
    /// least one remaining character.
    char next() {
        char c = peek();
        advanceOffset(1);
        return c;
    }

    /// Claim the next character if it exists and equals the given
    /// character.
    bool nextIf(char c) {
        if (isEmpty() || peek() != c)
            return false;
        advanceOffset(1);
        return true;
    }

    /// Claim the next few characters if they exactly match the given string.
    bool nextIf(StringRef str) {
        if (!Text.startswith(str))
            return false;
        advanceOffset(str.size());
        return true;
    }

    /// Return the next len characters without claiming them.  Asserts
    /// that there are at least so many characters.
    StringRef slice(size_t len) { return Text.substr(0, len); }

    /// Return the current string ref without claiming any characters.
    StringRef str() { return Text; }

    /// Claim the next len characters.
    void advanceOffset(size_t len) { Text = Text.substr(len); }

    /// Claim and return all the rest of the characters.
    StringRef getString() {
        auto result = Text;
        advanceOffset(Text.size());
        return result;
    }

    bool readUntil(char c, std::string &result) {
        llvm::Optional<char> c2;
        while (!isEmpty() && (c2 = peek()).getValue() != c) {
            result.push_back(c2.getValue());
            advanceOffset(1);
        }
        return c2.hasValue() && c2.getValue() == c;
    }
};

static StringRef toString(Directness d) {
    switch (d) {
        case Directness::Direct:
            return "direct";
        case Directness::Indirect:
            return "indirect";
    }
    unreachable("bad directness");
}

static StringRef toString(ValueWitnessKind k) {
    switch (k) {
        case ValueWitnessKind::AllocateBuffer:
            return "allocateBuffer";
        case ValueWitnessKind::AssignWithCopy:
            return "assignWithCopy";
        case ValueWitnessKind::AssignWithTake:
            return "assignWithTake";
        case ValueWitnessKind::DeallocateBuffer:
            return "deallocateBuffer";
        case ValueWitnessKind::Destroy:
            return "destroy";
        case ValueWitnessKind::DestroyBuffer:
            return "destroyBuffer";
        case ValueWitnessKind::InitializeBufferWithCopyOfBuffer:
            return "initializeBufferWithCopyOfBuffer";
        case ValueWitnessKind::InitializeBufferWithCopy:
            return "initializeBufferWithCopy";
        case ValueWitnessKind::InitializeWithCopy:
            return "initializeWithCopy";
        case ValueWitnessKind::InitializeBufferWithTake:
            return "initializeBufferWithTake";
        case ValueWitnessKind::InitializeWithTake:
            return "initializeWithTake";
        case ValueWitnessKind::ProjectBuffer:
            return "projectBuffer";
        case ValueWitnessKind::InitializeBufferWithTakeOfBuffer:
            return "initializeBufferWithTakeOfBuffer";
        case ValueWitnessKind::DestroyArray:
            return "destroyArray";
        case ValueWitnessKind::InitializeArrayWithCopy:
            return "initializeArrayWithCopy";
        case ValueWitnessKind::InitializeArrayWithTakeFrontToBack:
            return "initializeArrayWithTakeFrontToBack";
        case ValueWitnessKind::InitializeArrayWithTakeBackToFront:
            return "initializeArrayWithTakeBackToFront";
        case ValueWitnessKind::StoreExtraInhabitant:
            return "storeExtraInhabitant";
        case ValueWitnessKind::GetExtraInhabitantIndex:
            return "getExtraInhabitantIndex";
        case ValueWitnessKind::GetEnumTag:
            return "getEnumTag";
        case ValueWitnessKind::DestructiveProjectEnumData:
            return "destructiveProjectEnumData";
    }
    unreachable("bad value witness kind");
}

/// The main class for parsing a demangling tree out of a mangled string.
class Demangler {
    std::vector<NodePointer> Substitutions;
    NameSource Mangled;

public:
    Demangler(llvm::StringRef mangled) : Mangled(mangled) {}

/// Try to demangle a child node of the given kind.  If that fails,
/// return; otherwise add it to the parent.
#define DEMANGLE_CHILD_OR_RETURN(PARENT, CHILD_KIND) \
    do {                                             \
        auto _node = demangle##CHILD_KIND();         \
        if (!_node)                                  \
            return nullptr;                          \
        (PARENT)->addChild(std::move(_node));        \
    } while (false)

/// Try to demangle a child node of the given kind.  If that fails,
/// return; otherwise add it to the parent.
#define DEMANGLE_CHILD_AS_NODE_OR_RETURN(PARENT, CHILD_KIND)                               \
    do {                                                                                   \
        auto _kind = demangle##CHILD_KIND();                                               \
        if (!_kind.hasValue())                                                             \
            return nullptr;                                                                \
        (PARENT)->addChild(NodeFactory::create(Node::Kind::CHILD_KIND, unsigned(*_kind))); \
    } while (false)

    /// Attempt to demangle the source string.  The root node will
    /// always be a Global.  Extra characters at the end will be
    /// tolerated (and included as a Suffix node as a child of the
    /// Global).
    ///
    /// \return true if the mangling succeeded
    NodePointer demangleTopLevel() {
        if (!Mangled.nextIf("_T"))
            return nullptr;

        NodePointer topLevel = NodeFactory::create(Node::Kind::Global);

        // First demangle any specialization prefixes.
        if (Mangled.nextIf("TS")) {
            do {
                DEMANGLE_CHILD_OR_RETURN(topLevel, SpecializedAttribute);

                // The Substitution header does not share state with the rest
                // of the mangling.
                Substitutions.clear();
            } while (Mangled.nextIf("_TTS"));

            // Then check that we have a global.
            if (!Mangled.nextIf("_T"))
                return nullptr;

        } else if (Mangled.nextIf("To")) {
            topLevel->addChild(NodeFactory::create(Node::Kind::ObjCAttribute));
        } else if (Mangled.nextIf("TO")) {
            topLevel->addChild(NodeFactory::create(Node::Kind::NonObjCAttribute));
        } else if (Mangled.nextIf("TD")) {
            topLevel->addChild(NodeFactory::create(Node::Kind::DynamicAttribute));
        } else if (Mangled.nextIf("Td")) {
            topLevel->addChild(NodeFactory::create(Node::Kind::DirectMethodReferenceAttribute));
        } else if (Mangled.nextIf("TV")) {
            topLevel->addChild(NodeFactory::create(Node::Kind::VTableAttribute));
        }

        DEMANGLE_CHILD_OR_RETURN(topLevel, Global);

        // Add a suffix node if there's anything left unmangled.
        if (!Mangled.isEmpty()) {
            topLevel->addChild(NodeFactory::create(Node::Kind::Suffix, Mangled.getString()));
        }

        return topLevel;
    }

    NodePointer demangleTypeName() { return demangleType(); }

private:
    enum class IsVariadic { yes = true, no = false };

    Optional<Directness> demangleDirectness() {
        if (Mangled.nextIf('d'))
            return Directness::Direct;
        if (Mangled.nextIf('i'))
            return Directness::Indirect;
        return None;
    }

    bool demangleNatural(Node::IndexType &num) {
        if (!Mangled)
            return false;
        char c = Mangled.next();
        if (c < '0' || c > '9')
            return false;
        num = (Node::IndexType)(c - '0');
        while (true) {
            if (!Mangled) {
                return true;
            }
            c = Mangled.peek();
            if (c < '0' || c > '9') {
                return true;
            } else {
                num = ((Node::IndexType)10 * num) + (Node::IndexType)(c - '0');
            }
            Mangled.next();
        }
    }

    bool demangleBuiltinSize(Node::IndexType &num) {
        if (!demangleNatural(num))
            return false;
        if (Mangled.nextIf('_'))
            return true;
        return false;
    }

    Optional<ValueWitnessKind> demangleValueWitnessKind() {
        if (!Mangled)
            return None;
        char c1 = Mangled.next();
        if (!Mangled)
            return None;
        char c2 = Mangled.next();
        if (c1 == 'a' && c2 == 'l')
            return ValueWitnessKind::AllocateBuffer;
        if (c1 == 'c' && c2 == 'a')
            return ValueWitnessKind::AssignWithCopy;
        if (c1 == 't' && c2 == 'a')
            return ValueWitnessKind::AssignWithTake;
        if (c1 == 'd' && c2 == 'e')
            return ValueWitnessKind::DeallocateBuffer;
        if (c1 == 'x' && c2 == 'x')
            return ValueWitnessKind::Destroy;
        if (c1 == 'X' && c2 == 'X')
            return ValueWitnessKind::DestroyBuffer;
        if (c1 == 'C' && c2 == 'P')
            return ValueWitnessKind::InitializeBufferWithCopyOfBuffer;
        if (c1 == 'C' && c2 == 'p')
            return ValueWitnessKind::InitializeBufferWithCopy;
        if (c1 == 'c' && c2 == 'p')
            return ValueWitnessKind::InitializeWithCopy;
        if (c1 == 'C' && c2 == 'c')
            return ValueWitnessKind::InitializeArrayWithCopy;
        if (c1 == 'T' && c2 == 'K')
            return ValueWitnessKind::InitializeBufferWithTakeOfBuffer;
        if (c1 == 'T' && c2 == 'k')
            return ValueWitnessKind::InitializeBufferWithTake;
        if (c1 == 't' && c2 == 'k')
            return ValueWitnessKind::InitializeWithTake;
        if (c1 == 'T' && c2 == 't')
            return ValueWitnessKind::InitializeArrayWithTakeFrontToBack;
        if (c1 == 't' && c2 == 'T')
            return ValueWitnessKind::InitializeArrayWithTakeBackToFront;
        if (c1 == 'p' && c2 == 'r')
            return ValueWitnessKind::ProjectBuffer;
        if (c1 == 'X' && c2 == 'x')
            return ValueWitnessKind::DestroyArray;
        if (c1 == 'x' && c2 == 's')
            return ValueWitnessKind::StoreExtraInhabitant;
        if (c1 == 'x' && c2 == 'g')
            return ValueWitnessKind::GetExtraInhabitantIndex;
        if (c1 == 'u' && c2 == 'g')
            return ValueWitnessKind::GetEnumTag;
        if (c1 == 'u' && c2 == 'p')
            return ValueWitnessKind::DestructiveProjectEnumData;
        return None;
    }

    NodePointer demangleGlobal() {
        if (!Mangled)
            return nullptr;

        // Type metadata.
        if (Mangled.nextIf('M')) {
            if (Mangled.nextIf('P')) {
                auto pattern = NodeFactory::create(Node::Kind::GenericTypeMetadataPattern);
                DEMANGLE_CHILD_OR_RETURN(pattern, Type);
                return pattern;
            }
            if (Mangled.nextIf('a')) {
                auto accessor = NodeFactory::create(Node::Kind::TypeMetadataAccessFunction);
                DEMANGLE_CHILD_OR_RETURN(accessor, Type);
                return accessor;
            }
            if (Mangled.nextIf('L')) {
                auto cache = NodeFactory::create(Node::Kind::TypeMetadataLazyCache);
                DEMANGLE_CHILD_OR_RETURN(cache, Type);
                return cache;
            }
            if (Mangled.nextIf('m')) {
                auto metaclass = NodeFactory::create(Node::Kind::Metaclass);
                DEMANGLE_CHILD_OR_RETURN(metaclass, Type);
                return metaclass;
            }
            if (Mangled.nextIf('n')) {
                auto nominalType = NodeFactory::create(Node::Kind::NominalTypeDescriptor);
                DEMANGLE_CHILD_OR_RETURN(nominalType, Type);
                return nominalType;
            }
            if (Mangled.nextIf('f')) {
                auto metadata = NodeFactory::create(Node::Kind::FullTypeMetadata);
                DEMANGLE_CHILD_OR_RETURN(metadata, Type);
                return metadata;
            }
            if (Mangled.nextIf('p')) {
                auto metadata = NodeFactory::create(Node::Kind::ProtocolDescriptor);
                DEMANGLE_CHILD_OR_RETURN(metadata, ProtocolName);
                return metadata;
            }
            auto metadata = NodeFactory::create(Node::Kind::TypeMetadata);
            DEMANGLE_CHILD_OR_RETURN(metadata, Type);
            return metadata;
        }

        // Partial application thunks.
        if (Mangled.nextIf('P')) {
            if (!Mangled.nextIf('A'))
                return nullptr;
            Node::Kind kind = Node::Kind::PartialApplyForwarder;
            if (Mangled.nextIf('o'))
                kind = Node::Kind::PartialApplyObjCForwarder;
            auto forwarder = NodeFactory::create(kind);
            if (Mangled.nextIf("__T"))
                DEMANGLE_CHILD_OR_RETURN(forwarder, Global);
            return forwarder;
        }

        // Top-level types, for various consumers.
        if (Mangled.nextIf('t')) {
            auto type = NodeFactory::create(Node::Kind::TypeMangling);
            DEMANGLE_CHILD_OR_RETURN(type, Type);
            return type;
        }

        // Value witnesses.
        if (Mangled.nextIf('w')) {
            Optional<ValueWitnessKind> w = demangleValueWitnessKind();
            if (!w.hasValue())
                return nullptr;
            auto witness = NodeFactory::create(Node::Kind::ValueWitness, unsigned(w.getValue()));
            DEMANGLE_CHILD_OR_RETURN(witness, Type);
            return witness;
        }

        // Offsets, value witness tables, and protocol witnesses.
        if (Mangled.nextIf('W')) {
            if (Mangled.nextIf('V')) {
                auto witnessTable = NodeFactory::create(Node::Kind::ValueWitnessTable);
                DEMANGLE_CHILD_OR_RETURN(witnessTable, Type);
                return witnessTable;
            }
            if (Mangled.nextIf('o')) {
                auto witnessTableOffset = NodeFactory::create(Node::Kind::WitnessTableOffset);
                DEMANGLE_CHILD_OR_RETURN(witnessTableOffset, Entity);
                return witnessTableOffset;
            }
            if (Mangled.nextIf('v')) {
                auto fieldOffset = NodeFactory::create(Node::Kind::FieldOffset);
                DEMANGLE_CHILD_AS_NODE_OR_RETURN(fieldOffset, Directness);
                DEMANGLE_CHILD_OR_RETURN(fieldOffset, Entity);
                return fieldOffset;
            }
            if (Mangled.nextIf('P')) {
                auto witnessTable = NodeFactory::create(Node::Kind::ProtocolWitnessTable);
                DEMANGLE_CHILD_OR_RETURN(witnessTable, ProtocolConformance);
                return witnessTable;
            }
            if (Mangled.nextIf('G')) {
                auto witnessTable = NodeFactory::create(Node::Kind::GenericProtocolWitnessTable);
                DEMANGLE_CHILD_OR_RETURN(witnessTable, ProtocolConformance);
                return witnessTable;
            }
            if (Mangled.nextIf('I')) {
                auto witnessTable = NodeFactory::create(Node::Kind::GenericProtocolWitnessTableInstantiationFunction);
                DEMANGLE_CHILD_OR_RETURN(witnessTable, ProtocolConformance);
                return witnessTable;
            }
            if (Mangled.nextIf('l')) {
                auto accessor = NodeFactory::create(Node::Kind::LazyProtocolWitnessTableAccessor);
                DEMANGLE_CHILD_OR_RETURN(accessor, Type);
                DEMANGLE_CHILD_OR_RETURN(accessor, ProtocolConformance);
                return accessor;
            }
            if (Mangled.nextIf('L')) {
                auto accessor = NodeFactory::create(Node::Kind::LazyProtocolWitnessTableCacheVariable);
                DEMANGLE_CHILD_OR_RETURN(accessor, Type);
                DEMANGLE_CHILD_OR_RETURN(accessor, ProtocolConformance);
                return accessor;
            }
            if (Mangled.nextIf('a')) {
                auto tableTemplate = NodeFactory::create(Node::Kind::ProtocolWitnessTableAccessor);
                DEMANGLE_CHILD_OR_RETURN(tableTemplate, ProtocolConformance);
                return tableTemplate;
            }
            if (Mangled.nextIf('t')) {
                auto accessor = NodeFactory::create(Node::Kind::AssociatedTypeMetadataAccessor);
                DEMANGLE_CHILD_OR_RETURN(accessor, ProtocolConformance);
                DEMANGLE_CHILD_OR_RETURN(accessor, DeclName);
                return accessor;
            }
            if (Mangled.nextIf('T')) {
                auto accessor = NodeFactory::create(Node::Kind::AssociatedTypeWitnessTableAccessor);
                DEMANGLE_CHILD_OR_RETURN(accessor, ProtocolConformance);
                DEMANGLE_CHILD_OR_RETURN(accessor, DeclName);
                DEMANGLE_CHILD_OR_RETURN(accessor, ProtocolName);
                return accessor;
            }
            return nullptr;
        }

        // Other thunks.
        if (Mangled.nextIf('T')) {
            if (Mangled.nextIf('R')) {
                auto thunk = NodeFactory::create(Node::Kind::ReabstractionThunkHelper);
                if (!demangleReabstractSignature(thunk))
                    return nullptr;
                return thunk;
            }
            if (Mangled.nextIf('r')) {
                auto thunk = NodeFactory::create(Node::Kind::ReabstractionThunk);
                if (!demangleReabstractSignature(thunk))
                    return nullptr;
                return thunk;
            }
            if (Mangled.nextIf('W')) {
                NodePointer thunk = NodeFactory::create(Node::Kind::ProtocolWitness);
                DEMANGLE_CHILD_OR_RETURN(thunk, ProtocolConformance);
                // The entity is mangled in its own generic context.
                DEMANGLE_CHILD_OR_RETURN(thunk, Entity);
                return thunk;
            }
            return nullptr;
        }

        // Everything else is just an entity.
        return demangleEntity();
    }

    NodePointer demangleGenericSpecialization(NodePointer specialization) {
        while (!Mangled.nextIf('_')) {
            // Otherwise, we have another parameter. Demangle the type.
            NodePointer param = NodeFactory::create(Node::Kind::GenericSpecializationParam);
            DEMANGLE_CHILD_OR_RETURN(param, Type);

            // Then parse any conformances until we find an underscore. Pop off the
            // underscore since it serves as the end of our mangling list.
            while (!Mangled.nextIf('_')) {
                DEMANGLE_CHILD_OR_RETURN(param, ProtocolConformance);
            }

            // Add the parameter to our specialization list.
            specialization->addChild(param);
        }

        return specialization;
    }

/// TODO: This is an atrocity. Come up with a shorter name.
#define FUNCSIGSPEC_CREATE_PARAM_KIND(kind) \
    NodeFactory::create(Node::Kind::FunctionSignatureSpecializationParamKind, unsigned(FunctionSigSpecializationParamKind::kind))
#define FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(payload) NodeFactory::create(Node::Kind::FunctionSignatureSpecializationParamPayload, payload)

    bool demangleFuncSigSpecializationConstantProp(NodePointer parent) {
        // Then figure out what was actually constant propagated. First check if
        // we have a function.
        if (Mangled.nextIf("fr")) {
            // Demangle the identifier
            NodePointer name = demangleIdentifier();
            if (!name || !Mangled.nextIf('_'))
                return false;
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_KIND(ConstantPropFunction));
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(name->getText()));
            return true;
        }

        if (Mangled.nextIf('g')) {
            NodePointer name = demangleIdentifier();
            if (!name || !Mangled.nextIf('_'))
                return false;
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_KIND(ConstantPropGlobal));
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(name->getText()));
            return true;
        }

        if (Mangled.nextIf('i')) {
            std::string Str;
            if (!Mangled.readUntil('_', Str) || !Mangled.nextIf('_'))
                return false;
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_KIND(ConstantPropInteger));
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(Str));
            return true;
        }

        if (Mangled.nextIf("fl")) {
            std::string Str;
            if (!Mangled.readUntil('_', Str) || !Mangled.nextIf('_'))
                return false;
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_KIND(ConstantPropFloat));
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(Str));
            return true;
        }

        if (Mangled.nextIf("s")) {
            // Skip: 'e' encoding 'v' str. encoding is a 0 or 1 and str is a string of
            // length less than or equal to 32. We do not specialize strings with a
            // length greater than 32.
            if (!Mangled.nextIf('e'))
                return false;
            char encoding = Mangled.peek();
            if (encoding != '0' && encoding != '1')
                return false;
            std::string encodingStr;
            if (encoding == '0')
                encodingStr += "u8";
            else
                encodingStr += "u16";
            Mangled.advanceOffset(1);

            if (!Mangled.nextIf('v'))
                return false;
            NodePointer str = demangleIdentifier();
            if (!str || !Mangled.nextIf('_'))
                return false;

            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_KIND(ConstantPropString));
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(encodingStr));
            parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(str->getText()));
            return true;
        }

        unreachable("Unknown constant prop specialization");
    }

    bool demangleFuncSigSpecializationClosureProp(NodePointer parent) {
        // We don't actually demangle the function or types for now. But we do want
        // to signal that we specialized a closure.

        NodePointer name = demangleIdentifier();
        if (!name) {
            return false;
        }

        parent->addChild(FUNCSIGSPEC_CREATE_PARAM_KIND(ClosureProp));
        parent->addChild(FUNCSIGSPEC_CREATE_PARAM_PAYLOAD(name->getText()));

        // Then demangle types until we fail.
        NodePointer type;
        while (Mangled.peek() != '_' && (type = demangleType())) {
            parent->addChild(type);
        }

        // Eat last '_'
        if (!Mangled.nextIf('_'))
            return false;

        return true;
    }

    NodePointer demangleFunctionSignatureSpecialization(NodePointer specialization) {
        unsigned paramCount = 0;

        // Until we hit the last '_' in our specialization info...
        while (!Mangled.nextIf('_')) {
            // Create the parameter.
            NodePointer param = NodeFactory::create(Node::Kind::FunctionSignatureSpecializationParam, paramCount);

            // First handle options.
            if (Mangled.nextIf("n_")) {
                // Leave the parameter empty.
            } else if (Mangled.nextIf("cp")) {
                if (!demangleFuncSigSpecializationConstantProp(param))
                    return nullptr;
            } else if (Mangled.nextIf("cl")) {
                if (!demangleFuncSigSpecializationClosureProp(param))
                    return nullptr;
            } else if (Mangled.nextIf("i_")) {
                auto result = FUNCSIGSPEC_CREATE_PARAM_KIND(BoxToValue);
                if (!result)
                    return nullptr;
                param->addChild(result);
            } else if (Mangled.nextIf("k_")) {
                auto result = FUNCSIGSPEC_CREATE_PARAM_KIND(BoxToStack);
                if (!result)
                    return nullptr;
                param->addChild(result);
            } else {
                // Otherwise handle option sets.
                unsigned Value = 0;
                if (Mangled.nextIf('d')) {
                    Value |= unsigned(FunctionSigSpecializationParamKind::Dead);
                }

                if (Mangled.nextIf('g')) {
                    Value |= unsigned(FunctionSigSpecializationParamKind::OwnedToGuaranteed);
                }

                if (Mangled.nextIf('s')) {
                    Value |= unsigned(FunctionSigSpecializationParamKind::SROA);
                }

                if (!Mangled.nextIf('_'))
                    return nullptr;

                if (!Value)
                    return nullptr;

                auto result = NodeFactory::create(Node::Kind::FunctionSignatureSpecializationParamKind, Value);
                if (!result)
                    return nullptr;
                param->addChild(result);
            }

            specialization->addChild(param);
            paramCount++;
        }

        return specialization;
    }

#undef FUNCSIGSPEC_CREATE_PARAM_KIND
#undef FUNCSIGSPEC_CREATE_PARAM_PAYLOAD

    NodePointer demangleSpecializedAttribute() {
        bool isNotReAbstracted = false;
        if (Mangled.nextIf("g") || (isNotReAbstracted = Mangled.nextIf("r"))) {
            auto spec = NodeFactory::create(isNotReAbstracted ? Node::Kind::GenericSpecializationNotReAbstracted : Node::Kind::GenericSpecialization);

            // Create a node if the specialization is externally inlineable.
            if (Mangled.nextIf("q")) {
                auto kind = Node::Kind::SpecializationIsFragile;
                spec->addChild(NodeFactory::create(kind));
            }

            // Create a node for the pass id.
            spec->addChild(NodeFactory::create(Node::Kind::SpecializationPassID, unsigned(Mangled.next() - 48)));

            // And then mangle the generic specialization.
            return demangleGenericSpecialization(spec);
        }
        if (Mangled.nextIf("f")) {
            auto spec = NodeFactory::create(Node::Kind::FunctionSignatureSpecialization);

            // Create a node if the specialization is externally inlineable.
            if (Mangled.nextIf("q")) {
                auto kind = Node::Kind::SpecializationIsFragile;
                spec->addChild(NodeFactory::create(kind));
            }

            // Add the pass id.
            spec->addChild(NodeFactory::create(Node::Kind::SpecializationPassID, unsigned(Mangled.next() - 48)));

            // Then perform the function signature specialization.
            return demangleFunctionSignatureSpecialization(spec);
        }

        // We don't know how to handle this specialization.
        return nullptr;
    }

    NodePointer demangleDeclName() {
        // decl-name ::= local-decl-name
        // local-decl-name ::= 'L' index identifier
        if (Mangled.nextIf('L')) {
            NodePointer discriminator = demangleIndexAsNode();
            if (!discriminator)
                return nullptr;

            NodePointer name = demangleIdentifier();
            if (!name)
                return nullptr;

            NodePointer localName = NodeFactory::create(Node::Kind::LocalDeclName);
            localName->addChild(std::move(discriminator));
            localName->addChild(std::move(name));
            return localName;

        } else if (Mangled.nextIf('P')) {
            NodePointer discriminator = demangleIdentifier();
            if (!discriminator)
                return nullptr;

            NodePointer name = demangleIdentifier();
            if (!name)
                return nullptr;

            auto privateName = NodeFactory::create(Node::Kind::PrivateDeclName);
            privateName->addChildren(std::move(discriminator), std::move(name));
            return privateName;
        }

        // decl-name ::= identifier
        return demangleIdentifier();
    }

    NodePointer demangleIdentifier(Optional<Node::Kind> kind = None) {
        if (!Mangled)
            return nullptr;

        bool isPunycoded = Mangled.nextIf('X');
        std::string decodeBuffer;

        auto decode = [&](StringRef s) -> StringRef {
            if (!isPunycoded)
                return s;
            if (!Punycode::decodePunycodeUTF8(s, decodeBuffer))
                return {};
            return decodeBuffer;
        };

        bool isOperator = false;
        if (Mangled.nextIf('o')) {
            isOperator = true;
            // Operator identifiers aren't valid in the contexts that are
            // building more specific identifiers.
            if (kind.hasValue())
                return nullptr;

            char op_mode = Mangled.next();
            switch (op_mode) {
                case 'p':
                    kind = Node::Kind::PrefixOperator;
                    break;
                case 'P':
                    kind = Node::Kind::PostfixOperator;
                    break;
                case 'i':
                    kind = Node::Kind::InfixOperator;
                    break;
                default:
                    return nullptr;
            }
        }

        if (!kind.hasValue())
            kind = Node::Kind::Identifier;

        Node::IndexType length;
        if (!demangleNatural(length))
            return nullptr;
        if (!Mangled.hasAtLeast((size_t)length))
            return nullptr;

        StringRef identifier = Mangled.slice((size_t)length);
        Mangled.advanceOffset((size_t)length);

        // Decode Unicode identifiers.
        identifier = decode(identifier);
        if (identifier.empty())
            return nullptr;

        // Decode operator names.
        std::string opDecodeBuffer;
        if (isOperator) {
            // abcdefghijklmnopqrstuvwxyz
            static const char op_char_table[] = "& @/= >    <*!|+?%-~   ^ .";

            opDecodeBuffer.reserve(identifier.size());
            for (signed char c : identifier) {
                if (c < 0) {
                    // Pass through Unicode characters.
                    opDecodeBuffer.push_back(c);
                    continue;
                }
                if (c < 'a' || c > 'z')
                    return nullptr;
                char o = op_char_table[c - 'a'];
                if (o == ' ')
                    return nullptr;
                opDecodeBuffer.push_back(o);
            }
            identifier = opDecodeBuffer;
        }

        return NodeFactory::create(*kind, identifier);
    }

    bool demangleIndex(Node::IndexType &natural) {
        if (Mangled.nextIf('_')) {
            natural = 0;
            return true;
        }
        if (demangleNatural(natural)) {
            if (!Mangled.nextIf('_'))
                return false;
            natural++;
            return true;
        }
        return false;
    }

    /// Demangle an <index> and package it as a node of some kind.
    NodePointer demangleIndexAsNode(Node::Kind kind = Node::Kind::Number) {
        Node::IndexType index;
        if (!demangleIndex(index))
            return nullptr;
        return NodeFactory::create(kind, index);
    }

    NodePointer createSwiftType(Node::Kind typeKind, StringRef name) {
        NodePointer type = NodeFactory::create(typeKind);
        type->addChild(NodeFactory::create(Node::Kind::Module, STDLIB_NAME));
        type->addChild(NodeFactory::create(Node::Kind::Identifier, name));
        return type;
    }

    /// Demangle a <substitution>, given that we've already consumed the 'S'.
    NodePointer demangleSubstitutionIndex() {
        if (!Mangled)
            return nullptr;
        if (Mangled.nextIf('o'))
            return NodeFactory::create(Node::Kind::Module, MANGLING_MODULE_OBJC);
        if (Mangled.nextIf('C'))
            return NodeFactory::create(Node::Kind::Module, MANGLING_MODULE_C);
        if (Mangled.nextIf('a'))
            return createSwiftType(Node::Kind::Structure, "Array");
        if (Mangled.nextIf('b'))
            return createSwiftType(Node::Kind::Structure, "Bool");
        if (Mangled.nextIf('c'))
            return createSwiftType(Node::Kind::Structure, "UnicodeScalar");
        if (Mangled.nextIf('d'))
            return createSwiftType(Node::Kind::Structure, "Double");
        if (Mangled.nextIf('f'))
            return createSwiftType(Node::Kind::Structure, "Float");
        if (Mangled.nextIf('i'))
            return createSwiftType(Node::Kind::Structure, "Int");
        if (Mangled.nextIf('V'))
            return createSwiftType(Node::Kind::Structure, "UnsafeRawPointer");
        if (Mangled.nextIf('v'))
            return createSwiftType(Node::Kind::Structure, "UnsafeMutableRawPointer");
        if (Mangled.nextIf('P'))
            return createSwiftType(Node::Kind::Structure, "UnsafePointer");
        if (Mangled.nextIf('p'))
            return createSwiftType(Node::Kind::Structure, "UnsafeMutablePointer");
        if (Mangled.nextIf('q'))
            return createSwiftType(Node::Kind::Enum, "Optional");
        if (Mangled.nextIf('Q'))
            return createSwiftType(Node::Kind::Enum, "ImplicitlyUnwrappedOptional");
        if (Mangled.nextIf('R'))
            return createSwiftType(Node::Kind::Structure, "UnsafeBufferPointer");
        if (Mangled.nextIf('r'))
            return createSwiftType(Node::Kind::Structure, "UnsafeMutableBufferPointer");
        if (Mangled.nextIf('S'))
            return createSwiftType(Node::Kind::Structure, "String");
        if (Mangled.nextIf('u'))
            return createSwiftType(Node::Kind::Structure, "UInt");
        Node::IndexType index_sub;
        if (!demangleIndex(index_sub))
            return nullptr;
        if (index_sub >= Substitutions.size())
            return nullptr;
        return Substitutions[(size_t)index_sub];
    }

    NodePointer demangleModule() {
        if (Mangled.nextIf('s')) {
            return NodeFactory::create(Node::Kind::Module, STDLIB_NAME);
        }
        if (Mangled.nextIf('S')) {
            NodePointer module = demangleSubstitutionIndex();
            if (!module)
                return nullptr;
            if (module->getKind() != Node::Kind::Module)
                return nullptr;
            return module;
        }

        NodePointer module = demangleIdentifier(Node::Kind::Module);
        if (!module)
            return nullptr;
        Substitutions.push_back(module);
        return module;
    }

    NodePointer demangleDeclarationName(Node::Kind kind) {
        NodePointer context = demangleContext();
        if (!context)
            return nullptr;

        auto name = demangleDeclName();
        if (!name)
            return nullptr;

        auto decl = NodeFactory::create(kind);
        decl->addChild(context);
        decl->addChild(name);
        Substitutions.push_back(decl);
        return decl;
    }

    NodePointer demangleProtocolName() {
        NodePointer proto = demangleProtocolNameImpl();
        if (!proto)
            return nullptr;

        NodePointer type = NodeFactory::create(Node::Kind::Type);
        type->addChild(proto);
        return type;
    }

    NodePointer demangleProtocolNameGivenContext(NodePointer context) {
        NodePointer name = demangleDeclName();
        if (!name)
            return nullptr;

        auto proto = NodeFactory::create(Node::Kind::Protocol);
        proto->addChild(std::move(context));
        proto->addChild(std::move(name));
        Substitutions.push_back(proto);
        return proto;
    }

    NodePointer demangleProtocolNameImpl() {
        // There's an ambiguity in <protocol> between a substitution of
        // the protocol and a substitution of the protocol's context, so
        // we have to duplicate some of the logic from
        // demangleDeclarationName.
        if (Mangled.nextIf('S')) {
            NodePointer sub = demangleSubstitutionIndex();
            if (!sub)
                return nullptr;
            if (sub->getKind() == Node::Kind::Protocol)
                return sub;

            if (sub->getKind() != Node::Kind::Module)
                return nullptr;

            return demangleProtocolNameGivenContext(sub);
        }

        if (Mangled.nextIf('s')) {
            NodePointer stdlib = NodeFactory::create(Node::Kind::Module, STDLIB_NAME);

            return demangleProtocolNameGivenContext(stdlib);
        }

        return demangleDeclarationName(Node::Kind::Protocol);
    }

    NodePointer demangleNominalType() {
        if (Mangled.nextIf('S'))
            return demangleSubstitutionIndex();
        if (Mangled.nextIf('V'))
            return demangleDeclarationName(Node::Kind::Structure);
        if (Mangled.nextIf('O'))
            return demangleDeclarationName(Node::Kind::Enum);
        if (Mangled.nextIf('C'))
            return demangleDeclarationName(Node::Kind::Class);
        if (Mangled.nextIf('P'))
            return demangleDeclarationName(Node::Kind::Protocol);
        return nullptr;
    }

    NodePointer demangleBoundGenericArgs(NodePointer nominalType) {
        // Generic arguments for the outermost type come first.
        NodePointer parentOrModule = nominalType->getChild(0);

        if (parentOrModule->getKind() != Node::Kind::Module && parentOrModule->getKind() != Node::Kind::Function
            && parentOrModule->getKind() != Node::Kind::Extension) {
            parentOrModule = demangleBoundGenericArgs(parentOrModule);

            // Rebuild this type with the new parent type, which may have
            // had its generic arguments applied.
            NodePointer result = NodeFactory::create(nominalType->getKind());
            result->addChild(parentOrModule);
            result->addChild(nominalType->getChild(1));

            nominalType = result;
        }

        NodePointer args = NodeFactory::create(Node::Kind::TypeList);
        while (!Mangled.nextIf('_')) {
            NodePointer type = demangleType();
            if (!type)
                return nullptr;
            args->addChild(type);
            if (Mangled.isEmpty())
                return nullptr;
        }

        // If there were no arguments at this level there is nothing left
        // to do.
        if (args->getNumChildren() == 0)
            return nominalType;

        // Otherwise, build a bound generic type node from the unbound
        // type and arguments.
        NodePointer unboundType = NodeFactory::create(Node::Kind::Type);
        unboundType->addChild(nominalType);

        Node::Kind kind;
        switch (nominalType->getKind()) { // look through Type node
            case Node::Kind::Class:
                kind = Node::Kind::BoundGenericClass;
                break;
            case Node::Kind::Structure:
                kind = Node::Kind::BoundGenericStructure;
                break;
            case Node::Kind::Enum:
                kind = Node::Kind::BoundGenericEnum;
                break;
            default:
                return nullptr;
        }
        NodePointer result = NodeFactory::create(kind);
        result->addChild(unboundType);
        result->addChild(args);
        return result;
    }

    NodePointer demangleBoundGenericType() {
        // bound-generic-type ::= 'G' nominal-type (args+ '_')+
        //
        // Each level of nominal type nesting has its own list of arguments.

        NodePointer nominalType = demangleNominalType();
        if (!nominalType)
            return nullptr;

        return demangleBoundGenericArgs(nominalType);
    }

    NodePointer demangleContext() {
        // context ::= module
        // context ::= entity
        // context ::= 'E' module context (extension defined in a different module)
        // context ::= 'e' module context generic-signature (constrained extension)
        if (!Mangled)
            return nullptr;
        if (Mangled.nextIf('E')) {
            NodePointer ext = NodeFactory::create(Node::Kind::Extension);
            NodePointer def_module = demangleModule();
            if (!def_module)
                return nullptr;
            NodePointer type = demangleContext();
            if (!type)
                return nullptr;
            ext->addChild(def_module);
            ext->addChild(type);
            return ext;
        }
        if (Mangled.nextIf('e')) {
            NodePointer ext = NodeFactory::create(Node::Kind::Extension);
            NodePointer def_module = demangleModule();
            if (!def_module)
                return nullptr;
            NodePointer sig = demangleGenericSignature();
            // The generic context is currently re-specified by the type mangling.
            // If we ever remove 'self' from manglings, we should stop resetting the
            // context here.
            if (!sig)
                return nullptr;
            NodePointer type = demangleContext();
            if (!type)
                return nullptr;

            ext->addChild(def_module);
            ext->addChild(type);
            ext->addChild(sig);
            return ext;
        }
        if (Mangled.nextIf('S'))
            return demangleSubstitutionIndex();
        if (Mangled.nextIf('s'))
            return NodeFactory::create(Node::Kind::Module, STDLIB_NAME);
        if (Mangled.nextIf('G'))
            return demangleBoundGenericType();
        if (isStartOfEntity(Mangled.peek()))
            return demangleEntity();
        return demangleModule();
    }

    NodePointer demangleProtocolList() {
        NodePointer proto_list = NodeFactory::create(Node::Kind::ProtocolList);
        NodePointer type_list = NodeFactory::create(Node::Kind::TypeList);
        proto_list->addChild(type_list);
        while (!Mangled.nextIf('_')) {
            NodePointer proto = demangleProtocolName();
            if (!proto)
                return nullptr;
            type_list->addChild(std::move(proto));
        }
        return proto_list;
    }

    NodePointer demangleProtocolConformance() {
        NodePointer type = demangleType();
        if (!type)
            return nullptr;
        NodePointer protocol = demangleProtocolName();
        if (!protocol)
            return nullptr;
        NodePointer context = demangleContext();
        if (!context)
            return nullptr;
        NodePointer proto_conformance = NodeFactory::create(Node::Kind::ProtocolConformance);
        proto_conformance->addChild(type);
        proto_conformance->addChild(protocol);
        proto_conformance->addChild(context);
        return proto_conformance;
    }

    // entity ::= entity-kind context entity-name
    // entity ::= nominal-type
    NodePointer demangleEntity() {
        // static?
        bool isStatic = Mangled.nextIf('Z');

        // entity-kind
        Node::Kind entityBasicKind;
        if (Mangled.nextIf('F')) {
            entityBasicKind = Node::Kind::Function;
        } else if (Mangled.nextIf('v')) {
            entityBasicKind = Node::Kind::Variable;
        } else if (Mangled.nextIf('I')) {
            entityBasicKind = Node::Kind::Initializer;
        } else if (Mangled.nextIf('i')) {
            entityBasicKind = Node::Kind::Subscript;
        } else {
            return demangleNominalType();
        }

        NodePointer context = demangleContext();
        if (!context)
            return nullptr;

        // entity-name
        Node::Kind entityKind;
        bool hasType = true;
        NodePointer name;
        if (Mangled.nextIf('D')) {
            entityKind = Node::Kind::Deallocator;
            hasType = false;
        } else if (Mangled.nextIf('d')) {
            entityKind = Node::Kind::Destructor;
            hasType = false;
        } else if (Mangled.nextIf('e')) {
            entityKind = Node::Kind::IVarInitializer;
            hasType = false;
        } else if (Mangled.nextIf('E')) {
            entityKind = Node::Kind::IVarDestroyer;
            hasType = false;
        } else if (Mangled.nextIf('C')) {
            entityKind = Node::Kind::Allocator;
        } else if (Mangled.nextIf('c')) {
            entityKind = Node::Kind::Constructor;
        } else if (Mangled.nextIf('a')) {
            if (Mangled.nextIf('O')) {
                entityKind = Node::Kind::OwningMutableAddressor;
            } else if (Mangled.nextIf('o')) {
                entityKind = Node::Kind::NativeOwningMutableAddressor;
            } else if (Mangled.nextIf('p')) {
                entityKind = Node::Kind::NativePinningMutableAddressor;
            } else if (Mangled.nextIf('u')) {
                entityKind = Node::Kind::UnsafeMutableAddressor;
            } else {
                return nullptr;
            }
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('l')) {
            if (Mangled.nextIf('O')) {
                entityKind = Node::Kind::OwningAddressor;
            } else if (Mangled.nextIf('o')) {
                entityKind = Node::Kind::NativeOwningAddressor;
            } else if (Mangled.nextIf('p')) {
                entityKind = Node::Kind::NativePinningAddressor;
            } else if (Mangled.nextIf('u')) {
                entityKind = Node::Kind::UnsafeAddressor;
            } else {
                return nullptr;
            }
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('g')) {
            entityKind = Node::Kind::Getter;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('G')) {
            entityKind = Node::Kind::GlobalGetter;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('s')) {
            entityKind = Node::Kind::Setter;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('m')) {
            entityKind = Node::Kind::MaterializeForSet;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('w')) {
            entityKind = Node::Kind::WillSet;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('W')) {
            entityKind = Node::Kind::DidSet;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('U')) {
            entityKind = Node::Kind::ExplicitClosure;
            name = demangleIndexAsNode();
            if (!name)
                return nullptr;
        } else if (Mangled.nextIf('u')) {
            entityKind = Node::Kind::ImplicitClosure;
            name = demangleIndexAsNode();
            if (!name)
                return nullptr;
        } else if (entityBasicKind == Node::Kind::Initializer) {
            // entity-name ::= 'A' index
            if (Mangled.nextIf('A')) {
                entityKind = Node::Kind::DefaultArgumentInitializer;
                name = demangleIndexAsNode();
                if (!name)
                    return nullptr;
                // entity-name ::= 'i'
            } else if (Mangled.nextIf('i')) {
                entityKind = Node::Kind::Initializer;
            } else {
                return nullptr;
            }
            hasType = false;
        } else {
            entityKind = entityBasicKind;
            name = demangleDeclName();
            if (!name)
                return nullptr;
        }

        NodePointer entity = NodeFactory::create(entityKind);
        entity->addChild(context);

        if (name)
            entity->addChild(name);

        if (hasType) {
            auto type = demangleType();
            if (!type)
                return nullptr;
            entity->addChild(type);
        }

        if (isStatic) {
            auto staticNode = NodeFactory::create(Node::Kind::Static);
            staticNode->addChild(entity);
            return staticNode;
        }

        return entity;
    }

    NodePointer demangleArchetypeRef(Node::IndexType depth, Node::IndexType i) {
        // FIXME: Name won't match demangled context generic signatures correctly.
        auto ref = NodeFactory::create(Node::Kind::ArchetypeRef, archetypeName(i, depth));
        ref->addChild(NodeFactory::create(Node::Kind::Index, depth));
        ref->addChild(NodeFactory::create(Node::Kind::Index, i));
        return ref;
    }

    NodePointer getDependentGenericParamType(unsigned depth, unsigned index) {
        DemanglerPrinter PrintName;
        PrintName << archetypeName(index, depth);

        auto paramTy = NodeFactory::create(Node::Kind::DependentGenericParamType, std::move(PrintName).str());
        paramTy->addChild(NodeFactory::create(Node::Kind::Index, depth));
        paramTy->addChild(NodeFactory::create(Node::Kind::Index, index));

        return paramTy;
    }

    NodePointer demangleGenericParamIndex() {
        Node::IndexType depth, index;

        if (Mangled.nextIf('d')) {
            if (!demangleIndex(depth))
                return nullptr;
            depth += 1;
            if (!demangleIndex(index))
                return nullptr;
        } else if (Mangled.nextIf('x')) {
            depth = 0;
            index = 0;
        } else {
            if (!demangleIndex(index))
                return nullptr;
            depth = 0;
            index += 1;
        }
        return getDependentGenericParamType((unsigned)depth, (unsigned)index);
    }

    NodePointer demangleDependentMemberTypeName(NodePointer base) {
        assert(base->getKind() == Node::Kind::Type && "base should be a type");
        NodePointer assocTy;

        if (Mangled.nextIf('S')) {
            assocTy = demangleSubstitutionIndex();
            if (!assocTy)
                return nullptr;
            if (assocTy->getKind() != Node::Kind::DependentAssociatedTypeRef)
                return nullptr;
        } else {
            NodePointer protocol = nullptr;
            if (Mangled.nextIf('P')) {
                protocol = demangleProtocolName();
                if (!protocol)
                    return nullptr;
            }

            // TODO: If the protocol name was elided from the assoc type mangling,
            // we could try to fish it out of the generic signature constraints on the
            // base.
            assocTy = demangleIdentifier(Node::Kind::DependentAssociatedTypeRef);
            if (!assocTy)
                return nullptr;
            if (protocol)
                assocTy->addChild(protocol);

            Substitutions.push_back(assocTy);
        }

        NodePointer depTy = NodeFactory::create(Node::Kind::DependentMemberType);
        depTy->addChild(base);
        depTy->addChild(assocTy);
        return depTy;
    }

    NodePointer demangleAssociatedTypeSimple() {
        // Demangle the base type.
        auto base = demangleGenericParamIndex();
        if (!base)
            return nullptr;

        NodePointer nodeType = NodeFactory::create(Node::Kind::Type);
        nodeType->addChild(base);

        // Demangle the associated type name.
        return demangleDependentMemberTypeName(nodeType);
    }

    NodePointer demangleAssociatedTypeCompound() {
        // Demangle the base type.
        auto base = demangleGenericParamIndex();
        if (!base)
            return nullptr;

        // Demangle the associated type chain.
        while (!Mangled.nextIf('_')) {
            NodePointer nodeType = NodeFactory::create(Node::Kind::Type);
            nodeType->addChild(base);

            base = demangleDependentMemberTypeName(nodeType);
            if (!base)
                return nullptr;
        }

        return base;
    }

    NodePointer demangleDependentType() {
        if (!Mangled)
            return nullptr;

        // A dependent member type begins with a non-index, non-'d' character.
        auto c = Mangled.peek();
        if (c != 'd' && c != '_' && !isDigit(c)) {
            NodePointer baseType = demangleType();
            if (!baseType)
                return nullptr;
            return demangleDependentMemberTypeName(baseType);
        }

        // Otherwise, we have a generic parameter.
        return demangleGenericParamIndex();
    }

    NodePointer demangleConstrainedTypeImpl() {
        // The constrained type can only be a generic parameter or an associated
        // type thereof. The 'q' introducer is thus left off of generic params.
        if (Mangled.nextIf('w')) {
            return demangleAssociatedTypeSimple();
        }
        if (Mangled.nextIf('W')) {
            return demangleAssociatedTypeCompound();
        }
        return demangleGenericParamIndex();
    }

    NodePointer demangleConstrainedType() {
        auto type = demangleConstrainedTypeImpl();
        if (!type)
            return nullptr;

        NodePointer nodeType = NodeFactory::create(Node::Kind::Type);
        nodeType->addChild(type);
        return nodeType;
    }

    NodePointer demangleGenericSignature(bool isPseudogeneric = false) {
        auto sig = NodeFactory::create(isPseudogeneric ? Node::Kind::DependentPseudogenericSignature : Node::Kind::DependentGenericSignature);
        // First read in the parameter counts at each depth.
        Node::IndexType count = ~(Node::IndexType)0;

        auto addCount = [&] {
            auto countNode = NodeFactory::create(Node::Kind::DependentGenericParamCount, count);
            sig->addChild(countNode);
        };

        while (Mangled.peek() != 'R' && Mangled.peek() != 'r') {
            if (Mangled.nextIf('z')) {
                count = 0;
            } else if (demangleIndex(count)) {
                count += 1;
            } else {
                return nullptr;
            }
            addCount();
        }

        // No mangled parameters means we have exactly one.
        if (count == ~(Node::IndexType)0) {
            count = 1;
            addCount();
        }

        // Next read in the generic requirements, if any.
        if (Mangled.nextIf('r'))
            return sig;

        if (!Mangled.nextIf('R'))
            return nullptr;

        while (!Mangled.nextIf('r')) {
            NodePointer reqt = demangleGenericRequirement();
            if (!reqt)
                return nullptr;
            sig->addChild(reqt);
        }

        return sig;
    }

    NodePointer demangleMetatypeRepresentation() {
        if (Mangled.nextIf('t'))
            return NodeFactory::create(Node::Kind::MetatypeRepresentation, "@thin");

        if (Mangled.nextIf('T'))
            return NodeFactory::create(Node::Kind::MetatypeRepresentation, "@thick");

        if (Mangled.nextIf('o'))
            return NodeFactory::create(Node::Kind::MetatypeRepresentation, "@objc_metatype");

        unreachable("Unhandled metatype representation");
    }

    NodePointer demangleGenericRequirement() {
        NodePointer constrainedType = demangleConstrainedType();
        if (!constrainedType)
            return nullptr;
        if (Mangled.nextIf('z')) {
            NodePointer second = demangleType();
            if (!second)
                return nullptr;
            auto reqt = NodeFactory::create(Node::Kind::DependentGenericSameTypeRequirement);
            reqt->addChild(constrainedType);
            reqt->addChild(second);
            return reqt;
        }

        // Base class constraints are introduced by a class type mangling, which
        // will begin with either 'C' or 'S'.
        if (!Mangled)
            return nullptr;
        NodePointer constraint;

        auto next = Mangled.peek();

        if (next == 'C') {
            constraint = demangleType();
            if (!constraint)
                return nullptr;
        } else if (next == 'S') {
            // A substitution may be either the module name of a protocol or a full
            // type name.
            NodePointer typeName;
            Mangled.next();
            NodePointer sub = demangleSubstitutionIndex();
            if (!sub)
                return nullptr;
            if (sub->getKind() == Node::Kind::Protocol || sub->getKind() == Node::Kind::Class) {
                typeName = sub;
            } else if (sub->getKind() == Node::Kind::Module) {
                typeName = demangleProtocolNameGivenContext(sub);
                if (!typeName)
                    return nullptr;
            } else {
                return nullptr;
            }
            constraint = NodeFactory::create(Node::Kind::Type);
            constraint->addChild(typeName);
        } else {
            constraint = demangleProtocolName();
            if (!constraint)
                return nullptr;
        }
        auto reqt = NodeFactory::create(Node::Kind::DependentGenericConformanceRequirement);
        reqt->addChild(constrainedType);
        reqt->addChild(constraint);
        return reqt;
    }

    NodePointer demangleArchetypeType() {
        auto makeSelfType = [&](NodePointer proto) -> NodePointer {
            auto selfType = NodeFactory::create(Node::Kind::SelfTypeRef);
            selfType->addChild(proto);
            Substitutions.push_back(selfType);
            return selfType;
        };

        auto makeAssociatedType = [&](NodePointer root) -> NodePointer {
            NodePointer name = demangleIdentifier();
            if (!name)
                return nullptr;
            auto assocType = NodeFactory::create(Node::Kind::AssociatedTypeRef);
            assocType->addChild(root);
            assocType->addChild(name);
            Substitutions.push_back(assocType);
            return assocType;
        };

        if (Mangled.nextIf('P')) {
            NodePointer proto = demangleProtocolName();
            if (!proto)
                return nullptr;
            return makeSelfType(proto);
        }

        if (Mangled.nextIf('Q')) {
            NodePointer root = demangleArchetypeType();
            if (!root)
                return nullptr;
            return makeAssociatedType(root);
        }
        if (Mangled.nextIf('S')) {
            NodePointer sub = demangleSubstitutionIndex();
            if (!sub)
                return nullptr;
            if (sub->getKind() == Node::Kind::Protocol)
                return makeSelfType(sub);
            else
                return makeAssociatedType(sub);
        }
        if (Mangled.nextIf('s')) {
            NodePointer stdlib = NodeFactory::create(Node::Kind::Module, STDLIB_NAME);
            return makeAssociatedType(stdlib);
        }
        if (Mangled.nextIf('d')) {
            Node::IndexType depth, index;
            if (!demangleIndex(depth))
                return nullptr;
            if (!demangleIndex(index))
                return nullptr;
            return demangleArchetypeRef(depth + 1, index);
        }
        if (Mangled.nextIf('q')) {
            NodePointer index = demangleIndexAsNode();
            if (!index)
                return nullptr;
            NodePointer decl_ctx = NodeFactory::create(Node::Kind::DeclContext);
            NodePointer ctx = demangleContext();
            if (!ctx)
                return nullptr;
            decl_ctx->addChild(ctx);
            auto qual_atype = NodeFactory::create(Node::Kind::QualifiedArchetype);
            qual_atype->addChild(index);
            qual_atype->addChild(decl_ctx);
            return qual_atype;
        }
        Node::IndexType index;
        if (!demangleIndex(index))
            return nullptr;
        return demangleArchetypeRef(0, index);
    }

    NodePointer demangleTuple(IsVariadic isV) {
        NodePointer tuple = NodeFactory::create(isV == IsVariadic::yes ? Node::Kind::VariadicTuple : Node::Kind::NonVariadicTuple);
        while (!Mangled.nextIf('_')) {
            if (!Mangled)
                return nullptr;
            NodePointer elt = NodeFactory::create(Node::Kind::TupleElement);

            if (isStartOfIdentifier(Mangled.peek())) {
                NodePointer label = demangleIdentifier(Node::Kind::TupleElementName);
                if (!label)
                    return nullptr;
                elt->addChild(label);
            }

            NodePointer type = demangleType();
            if (!type)
                return nullptr;
            elt->addChild(type);

            tuple->addChild(elt);
        }
        return tuple;
    }

    NodePointer postProcessReturnTypeNode(NodePointer out_args) {
        NodePointer out_node = NodeFactory::create(Node::Kind::ReturnType);
        out_node->addChild(out_args);
        return out_node;
    }

    NodePointer demangleType() {
        NodePointer type = demangleTypeImpl();
        if (!type)
            return nullptr;
        NodePointer nodeType = NodeFactory::create(Node::Kind::Type);
        nodeType->addChild(type);
        return nodeType;
    }

    NodePointer demangleFunctionType(Node::Kind kind) {
        bool throws = false;
        if (Mangled && Mangled.nextIf('z')) {
            throws = true;
        }
        NodePointer in_args = demangleType();
        if (!in_args)
            return nullptr;
        NodePointer out_args = demangleType();
        if (!out_args)
            return nullptr;
        NodePointer block = NodeFactory::create(kind);

        if (throws) {
            block->addChild(NodeFactory::create(Node::Kind::ThrowsAnnotation));
        }

        NodePointer in_node = NodeFactory::create(Node::Kind::ArgumentTuple);
        block->addChild(in_node);
        in_node->addChild(in_args);
        block->addChild(postProcessReturnTypeNode(out_args));
        return block;
    }

    NodePointer demangleTypeImpl() {
        if (!Mangled)
            return nullptr;
        char c = Mangled.next();
        if (c == 'B') {
            if (!Mangled)
                return nullptr;
            c = Mangled.next();
            if (c == 'b')
                return NodeFactory::create(Node::Kind::BuiltinTypeName, "Builtin.BridgeObject");
            if (c == 'B')
                return NodeFactory::create(Node::Kind::BuiltinTypeName, "Builtin.UnsafeValueBuffer");
            if (c == 'f') {
                Node::IndexType size;
                if (demangleBuiltinSize(size)) {
                    return NodeFactory::create(Node::Kind::BuiltinTypeName, std::move(DemanglerPrinter() << "Builtin.Float" << size).str());
                }
            }
            if (c == 'i') {
                Node::IndexType size;
                if (demangleBuiltinSize(size)) {
                    return NodeFactory::create(Node::Kind::BuiltinTypeName, (DemanglerPrinter() << "Builtin.Int" << size).str());
                }
            }
            if (c == 'v') {
                Node::IndexType elts;
                if (demangleNatural(elts)) {
                    if (!Mangled.nextIf('B'))
                        return nullptr;
                    if (Mangled.nextIf('i')) {
                        Node::IndexType size;
                        if (!demangleBuiltinSize(size))
                            return nullptr;
                        return NodeFactory::create(Node::Kind::BuiltinTypeName,
                                                   (DemanglerPrinter() << "Builtin.Vec" << elts << "xInt" << size).str());
                    }
                    if (Mangled.nextIf('f')) {
                        Node::IndexType size;
                        if (!demangleBuiltinSize(size))
                            return nullptr;
                        return NodeFactory::create(Node::Kind::BuiltinTypeName,
                                                   (DemanglerPrinter() << "Builtin.Vec" << elts << "xFloat" << size).str());
                    }
                    if (Mangled.nextIf('p'))
                        return NodeFactory::create(Node::Kind::BuiltinTypeName, (DemanglerPrinter() << "Builtin.Vec" << elts << "xRawPointer").str());
                }
            }
            if (c == 'O')
                return NodeFactory::create(Node::Kind::BuiltinTypeName, "Builtin.UnknownObject");
            if (c == 'o')
                return NodeFactory::create(Node::Kind::BuiltinTypeName, "Builtin.NativeObject");
            if (c == 'p')
                return NodeFactory::create(Node::Kind::BuiltinTypeName, "Builtin.RawPointer");
            if (c == 'w')
                return NodeFactory::create(Node::Kind::BuiltinTypeName, "Builtin.Word");
            return nullptr;
        }
        if (c == 'a')
            return demangleDeclarationName(Node::Kind::TypeAlias);

        if (c == 'b') {
            return demangleFunctionType(Node::Kind::ObjCBlock);
        }
        if (c == 'c') {
            return demangleFunctionType(Node::Kind::CFunctionPointer);
        }
        if (c == 'D') {
            NodePointer type = demangleType();
            if (!type)
                return nullptr;

            NodePointer dynamicSelf = NodeFactory::create(Node::Kind::DynamicSelf);
            dynamicSelf->addChild(type);
            return dynamicSelf;
        }
        if (c == 'E') {
            if (!Mangled.nextIf('R'))
                return nullptr;
            if (!Mangled.nextIf('R'))
                return nullptr;
            return NodeFactory::create(Node::Kind::ErrorType, std::string());
        }
        if (c == 'F') {
            return demangleFunctionType(Node::Kind::FunctionType);
        }
        if (c == 'f') {
            return demangleFunctionType(Node::Kind::UncurriedFunctionType);
        }
        if (c == 'G') {
            return demangleBoundGenericType();
        }
        if (c == 'X') {
            if (Mangled.nextIf('b')) {
                NodePointer type = demangleType();
                if (!type)
                    return nullptr;
                NodePointer boxType = NodeFactory::create(Node::Kind::SILBoxType);
                boxType->addChild(type);
                return boxType;
            }
        }
        if (c == 'K') {
            return demangleFunctionType(Node::Kind::AutoClosureType);
        }
        if (c == 'M') {
            NodePointer type = demangleType();
            if (!type)
                return nullptr;
            NodePointer metatype = NodeFactory::create(Node::Kind::Metatype);
            metatype->addChild(type);
            return metatype;
        }
        if (c == 'X') {
            if (Mangled.nextIf('M')) {
                NodePointer metatypeRepr = demangleMetatypeRepresentation();
                if (!metatypeRepr)
                    return nullptr;

                NodePointer type = demangleType();
                if (!type)
                    return nullptr;
                NodePointer metatype = NodeFactory::create(Node::Kind::Metatype);
                metatype->addChild(metatypeRepr);
                metatype->addChild(type);
                return metatype;
            }
        }
        if (c == 'P') {
            if (Mangled.nextIf('M')) {
                NodePointer type = demangleType();
                if (!type)
                    return nullptr;
                auto metatype = NodeFactory::create(Node::Kind::ExistentialMetatype);
                metatype->addChild(type);
                return metatype;
            }

            return demangleProtocolList();
        }

        if (c == 'X') {
            if (Mangled.nextIf('P')) {
                if (Mangled.nextIf('M')) {
                    NodePointer metatypeRepr = demangleMetatypeRepresentation();
                    if (!metatypeRepr)
                        return nullptr;

                    NodePointer type = demangleType();
                    if (!type)
                        return nullptr;

                    auto metatype = NodeFactory::create(Node::Kind::ExistentialMetatype);
                    metatype->addChild(metatypeRepr);
                    metatype->addChild(type);
                    return metatype;
                }

                return demangleProtocolList();
            }
        }
        if (c == 'Q') {
            return demangleArchetypeType();
        }
        if (c == 'q') {
            return demangleDependentType();
        }
        if (c == 'x') {
            // Special mangling for the first generic param.
            return getDependentGenericParamType(0, 0);
        }
        if (c == 'w') {
            return demangleAssociatedTypeSimple();
        }
        if (c == 'W') {
            return demangleAssociatedTypeCompound();
        }
        if (c == 'R') {
            NodePointer inout = NodeFactory::create(Node::Kind::InOut);
            NodePointer type = demangleTypeImpl();
            if (!type)
                return nullptr;
            inout->addChild(type);
            return inout;
        }
        if (c == 'S') {
            return demangleSubstitutionIndex();
        }
        if (c == 'T') {
            return demangleTuple(IsVariadic::no);
        }
        if (c == 't') {
            return demangleTuple(IsVariadic::yes);
        }
        if (c == 'u') {
            NodePointer sig = demangleGenericSignature();
            if (!sig)
                return nullptr;
            NodePointer sub = demangleType();
            if (!sub)
                return nullptr;
            NodePointer dependentGenericType = NodeFactory::create(Node::Kind::DependentGenericType);
            dependentGenericType->addChild(sig);
            dependentGenericType->addChild(sub);
            return dependentGenericType;
        }
        if (c == 'X') {
            if (Mangled.nextIf('f')) {
                return demangleFunctionType(Node::Kind::ThinFunctionType);
            }
            if (Mangled.nextIf('o')) {
                NodePointer type = demangleType();
                if (!type)
                    return nullptr;
                NodePointer unowned = NodeFactory::create(Node::Kind::Unowned);
                unowned->addChild(type);
                return unowned;
            }
            if (Mangled.nextIf('u')) {
                NodePointer type = demangleType();
                if (!type)
                    return nullptr;
                NodePointer unowned = NodeFactory::create(Node::Kind::Unmanaged);
                unowned->addChild(type);
                return unowned;
            }
            if (Mangled.nextIf('w')) {
                NodePointer type = demangleType();
                if (!type)
                    return nullptr;
                NodePointer weak = NodeFactory::create(Node::Kind::Weak);
                weak->addChild(type);
                return weak;
            }

            // type ::= 'XF' impl-function-type
            if (Mangled.nextIf('F')) {
                return demangleImplFunctionType();
            }

            return nullptr;
        }
        if (isStartOfNominalType(c))
            return demangleDeclarationName(nominalTypeMarkerToNodeKind(c));
        return nullptr;
    }

    bool demangleReabstractSignature(NodePointer signature) {
        if (Mangled.nextIf('G')) {
            NodePointer generics = demangleGenericSignature();
            if (!generics)
                return false;
            signature->addChild(std::move(generics));
        }

        NodePointer srcType = demangleType();
        if (!srcType)
            return false;
        signature->addChild(std::move(srcType));

        NodePointer destType = demangleType();
        if (!destType)
            return false;
        signature->addChild(std::move(destType));

        return true;
    }

    // impl-function-type ::= impl-callee-convention impl-function-attribute*
    //                        generics? '_' impl-parameter* '_' impl-result* '_'
    // impl-function-attribute ::= 'Cb'            // compatible with C block invocation function
    // impl-function-attribute ::= 'Cc'            // compatible with C global function
    // impl-function-attribute ::= 'Cm'            // compatible with Swift method
    // impl-function-attribute ::= 'CO'            // compatible with ObjC method
    // impl-function-attribute ::= 'Cw'            // compatible with protocol witness
    // impl-function-attribute ::= 'G'             // generic
    NodePointer demangleImplFunctionType() {
        NodePointer type = NodeFactory::create(Node::Kind::ImplFunctionType);

        if (!demangleImplCalleeConvention(type))
            return nullptr;

        if (Mangled.nextIf('C')) {
            if (Mangled.nextIf('b'))
                addImplFunctionAttribute(type, "@convention(block)");
            else if (Mangled.nextIf('c'))
                addImplFunctionAttribute(type, "@convention(c)");
            else if (Mangled.nextIf('m'))
                addImplFunctionAttribute(type, "@convention(method)");
            else if (Mangled.nextIf('O'))
                addImplFunctionAttribute(type, "@convention(objc_method)");
            else if (Mangled.nextIf('w'))
                addImplFunctionAttribute(type, "@convention(witness_method)");
            else
                return nullptr;
        }

        // Enter a new generic context if this type is generic.
        // FIXME: replace with std::optional, when we have it.
        bool isPseudogeneric = false;
        if (Mangled.nextIf('G') || (isPseudogeneric = Mangled.nextIf('g'))) {
            NodePointer generics = demangleGenericSignature(isPseudogeneric);
            if (!generics)
                return nullptr;
            type->addChild(generics);
        }

        // Expect the attribute terminator.
        if (!Mangled.nextIf('_'))
            return nullptr;

        // Demangle the parameters.
        if (!demangleImplParameters(type))
            return nullptr;

        // Demangle the result type.
        if (!demangleImplResults(type))
            return nullptr;

        return type;
    }

    enum class ImplConventionContext { Callee, Parameter, Result };

    /// impl-convention ::= 'a'                     // direct, autoreleased
    /// impl-convention ::= 'd'                     // direct, no ownership transfer
    /// impl-convention ::= 'D'                     // direct, no ownership transfer,
    ///                                             // dependent on self
    /// impl-convention ::= 'g'                     // direct, guaranteed
    /// impl-convention ::= 'e'                     // direct, deallocating
    /// impl-convention ::= 'i'                     // indirect, ownership transfer
    /// impl-convention ::= 'l'                     // indirect, inout
    /// impl-convention ::= 'o'                     // direct, ownership transfer
    ///
    /// Returns an empty string otherwise.
    StringRef demangleImplConvention(ImplConventionContext ctxt) {
#define CASE(CHAR, FOR_CALLEE, FOR_PARAMETER, FOR_RESULT) \
    if (Mangled.nextIf(CHAR)) {                           \
        switch (ctxt) {                                   \
            case ImplConventionContext::Callee:           \
                return (FOR_CALLEE);                      \
            case ImplConventionContext::Parameter:        \
                return (FOR_PARAMETER);                   \
            case ImplConventionContext::Result:           \
                return (FOR_RESULT);                      \
        }                                                 \
        unreachable("bad context");                       \
    }
        auto Nothing = StringRef();
        CASE('a', Nothing, Nothing, "@autoreleased")
        CASE('d', "@callee_unowned", "@unowned", "@unowned")
        CASE('D', Nothing, Nothing, "@unowned_inner_pointer")
        CASE('g', "@callee_guaranteed", "@guaranteed", Nothing)
        CASE('e', Nothing, "@deallocating", Nothing)
        CASE('i', Nothing, "@in", "@out")
        CASE('l', Nothing, "@inout", Nothing)
        CASE('o', "@callee_owned", "@owned", "@owned")
        return Nothing;
#undef CASE
    }

    // impl-callee-convention ::= 't'
    // impl-callee-convention ::= impl-convention
    bool demangleImplCalleeConvention(NodePointer type) {
        StringRef attr;
        if (Mangled.nextIf('t')) {
            attr = "@convention(thin)";
        } else {
            attr = demangleImplConvention(ImplConventionContext::Callee);
        }
        if (attr.empty()) {
            return false;
        }
        type->addChild(NodeFactory::create(Node::Kind::ImplConvention, attr));
        return true;
    }

    void addImplFunctionAttribute(NodePointer parent, StringRef attr, Node::Kind kind = Node::Kind::ImplFunctionAttribute) {
        parent->addChild(NodeFactory::create(kind, attr));
    }

    // impl-parameter ::= impl-convention type
    bool demangleImplParameters(NodePointer parent) {
        while (!Mangled.nextIf('_')) {
            auto input = demangleImplParameterOrResult(Node::Kind::ImplParameter);
            if (!input)
                return false;
            parent->addChild(input);
        }
        return true;
    }

    // impl-result ::= impl-convention type
    bool demangleImplResults(NodePointer parent) {
        while (!Mangled.nextIf('_')) {
            auto res = demangleImplParameterOrResult(Node::Kind::ImplResult);
            if (!res)
                return false;
            parent->addChild(res);
        }
        return true;
    }

    NodePointer demangleImplParameterOrResult(Node::Kind kind) {
        if (Mangled.nextIf('z')) {
            // Only valid for a result.
            if (kind != Node::Kind::ImplResult)
                return nullptr;
            kind = Node::Kind::ImplErrorResult;
        }

        auto getContext = [](Node::Kind aKind) -> ImplConventionContext {
            if (aKind == Node::Kind::ImplParameter)
                return ImplConventionContext::Parameter;
            else if (aKind == Node::Kind::ImplResult || aKind == Node::Kind::ImplErrorResult)
                return ImplConventionContext::Result;
            else
                unreachable("unexpected node kind");
        };

        auto convention = demangleImplConvention(getContext(kind));
        if (convention.empty())
            return nullptr;
        auto type = demangleType();
        if (!type)
            return nullptr;

        NodePointer node = NodeFactory::create(kind);
        node->addChild(NodeFactory::create(Node::Kind::ImplConvention, convention));
        node->addChild(type);

        return node;
    }
};
} // end anonymous namespace

NodePointer swift::Demangle::demangleSymbolAsNode(const char *MangledName, size_t MangledNameLength, __unused const DemangleOptions &Options) {
    Demangler demangler(StringRef(MangledName, MangledNameLength));
    return demangler.demangleTopLevel();
}

NodePointer swift::Demangle::demangleTypeAsNode(const char *MangledName, size_t MangledNameLength, __unused const DemangleOptions &Options) {
    Demangler demangler(StringRef(MangledName, MangledNameLength));
    return demangler.demangleTypeName();
}

namespace {
class NodePrinter {
private:
    DemanglerPrinter Printer;
    DemangleOptions Options;

public:
    NodePrinter(DemangleOptions options) : Options(options) {}

    std::string printRoot(NodePointer root) {
        print(root);
        return std::move(Printer).str();
    }

private:
    void printChildren(Node::iterator begin, Node::iterator end, const char *sep = nullptr) {
        for (; begin != end;) {
            print(*begin);
            ++begin;
            if (sep && begin != end)
                Printer << sep;
        }
    }

    void printChildren(NodePointer pointer, const char *sep = nullptr) {
        if (!pointer)
            return;
        Node::iterator begin = pointer->begin(), end = pointer->end();
        printChildren(begin, end, sep);
    }

    NodePointer getFirstChildOfKind(NodePointer pointer, Node::Kind kind) {
        if (!pointer)
            return nullptr;
        for (NodePointer &child : *pointer) {
            if (child && child->getKind() == kind)
                return child;
        }
        return nullptr;
    }

    void printBoundGenericNoSugar(NodePointer pointer) {
        if (pointer->getNumChildren() < 2)
            return;
        NodePointer typelist = pointer->getChild(1);
        print(pointer->getChild(0));
        Printer << "<";
        printChildren(typelist, ", ");
        Printer << ">";
    }

    static bool isSwiftModule(NodePointer node) { return (node->getKind() == Node::Kind::Module && node->getText() == STDLIB_NAME); }

    static bool isDebuggerGeneratedModule(NodePointer node) {
        return (node->getKind() == Node::Kind::Module && 0 == node->getText().find(LLDB_EXPRESSIONS_MODULE_NAME_PREFIX));
    }

    static bool isIdentifier(NodePointer node, StringRef desired) {
        return (node->getKind() == Node::Kind::Identifier && node->getText() == desired);
    }

    enum class SugarType { None, Optional, ImplicitlyUnwrappedOptional, Array, Dictionary };

    /// Determine whether this is a "simple" type, from the type-simple
    /// production.
    bool isSimpleType(NodePointer pointer) {
        switch (pointer->getKind()) {
            case Node::Kind::Archetype:
            case Node::Kind::ArchetypeRef:
            case Node::Kind::AssociatedType:
            case Node::Kind::AssociatedTypeRef:
            case Node::Kind::BoundGenericClass:
            case Node::Kind::BoundGenericEnum:
            case Node::Kind::BoundGenericStructure:
            case Node::Kind::BuiltinTypeName:
            case Node::Kind::Class:
            case Node::Kind::DependentGenericType:
            case Node::Kind::DependentMemberType:
            case Node::Kind::DependentGenericParamType:
            case Node::Kind::DynamicSelf:
            case Node::Kind::Enum:
            case Node::Kind::ErrorType:
            case Node::Kind::ExistentialMetatype:
            case Node::Kind::Metatype:
            case Node::Kind::MetatypeRepresentation:
            case Node::Kind::Module:
            case Node::Kind::NonVariadicTuple:
            case Node::Kind::Protocol:
            case Node::Kind::QualifiedArchetype:
            case Node::Kind::ReturnType:
            case Node::Kind::SelfTypeRef:
            case Node::Kind::SILBoxType:
            case Node::Kind::Structure:
            case Node::Kind::TupleElementName:
            case Node::Kind::Type:
            case Node::Kind::TypeAlias:
            case Node::Kind::TypeList:
            case Node::Kind::VariadicTuple:
                return true;

            case Node::Kind::Allocator:
            case Node::Kind::ArgumentTuple:
            case Node::Kind::AssociatedTypeMetadataAccessor:
            case Node::Kind::AssociatedTypeWitnessTableAccessor:
            case Node::Kind::AutoClosureType:
            case Node::Kind::CFunctionPointer:
            case Node::Kind::Constructor:
            case Node::Kind::Deallocator:
            case Node::Kind::DeclContext:
            case Node::Kind::DefaultArgumentInitializer:
            case Node::Kind::DependentAssociatedTypeRef:
            case Node::Kind::DependentGenericSignature:
            case Node::Kind::DependentGenericParamCount:
            case Node::Kind::DependentGenericConformanceRequirement:
            case Node::Kind::DependentGenericSameTypeRequirement:
            case Node::Kind::DependentPseudogenericSignature:
            case Node::Kind::Destructor:
            case Node::Kind::DidSet:
            case Node::Kind::DirectMethodReferenceAttribute:
            case Node::Kind::Directness:
            case Node::Kind::DynamicAttribute:
            case Node::Kind::ExplicitClosure:
            case Node::Kind::Extension:
            case Node::Kind::FieldOffset:
            case Node::Kind::FullTypeMetadata:
            case Node::Kind::Function:
            case Node::Kind::FunctionSignatureSpecialization:
            case Node::Kind::FunctionSignatureSpecializationParam:
            case Node::Kind::FunctionSignatureSpecializationParamKind:
            case Node::Kind::FunctionSignatureSpecializationParamPayload:
            case Node::Kind::FunctionType:
            case Node::Kind::GenericProtocolWitnessTable:
            case Node::Kind::GenericProtocolWitnessTableInstantiationFunction:
            case Node::Kind::GenericSpecialization:
            case Node::Kind::GenericSpecializationNotReAbstracted:
            case Node::Kind::GenericSpecializationParam:
            case Node::Kind::GenericTypeMetadataPattern:
            case Node::Kind::Getter:
            case Node::Kind::Global:
            case Node::Kind::GlobalGetter:
            case Node::Kind::Identifier:
            case Node::Kind::Index:
            case Node::Kind::IVarInitializer:
            case Node::Kind::IVarDestroyer:
            case Node::Kind::ImplConvention:
            case Node::Kind::ImplFunctionAttribute:
            case Node::Kind::ImplFunctionType:
            case Node::Kind::ImplicitClosure:
            case Node::Kind::ImplParameter:
            case Node::Kind::ImplResult:
            case Node::Kind::ImplErrorResult:
            case Node::Kind::InOut:
            case Node::Kind::InfixOperator:
            case Node::Kind::Initializer:
            case Node::Kind::LazyProtocolWitnessTableAccessor:
            case Node::Kind::LazyProtocolWitnessTableCacheVariable:
            case Node::Kind::LocalDeclName:
            case Node::Kind::PrivateDeclName:
            case Node::Kind::MaterializeForSet:
            case Node::Kind::Metaclass:
            case Node::Kind::NativeOwningAddressor:
            case Node::Kind::NativeOwningMutableAddressor:
            case Node::Kind::NativePinningAddressor:
            case Node::Kind::NativePinningMutableAddressor:
            case Node::Kind::NominalTypeDescriptor:
            case Node::Kind::NonObjCAttribute:
            case Node::Kind::Number:
            case Node::Kind::ObjCAttribute:
            case Node::Kind::ObjCBlock:
            case Node::Kind::OwningAddressor:
            case Node::Kind::OwningMutableAddressor:
            case Node::Kind::PartialApplyForwarder:
            case Node::Kind::PartialApplyObjCForwarder:
            case Node::Kind::PostfixOperator:
            case Node::Kind::PrefixOperator:
            case Node::Kind::ProtocolConformance:
            case Node::Kind::ProtocolDescriptor:
            case Node::Kind::ProtocolList:
            case Node::Kind::ProtocolWitness:
            case Node::Kind::ProtocolWitnessTable:
            case Node::Kind::ProtocolWitnessTableAccessor:
            case Node::Kind::ReabstractionThunk:
            case Node::Kind::ReabstractionThunkHelper:
            case Node::Kind::Setter:
            case Node::Kind::SpecializationIsFragile:
            case Node::Kind::SpecializationPassID:
            case Node::Kind::Static:
            case Node::Kind::Subscript:
            case Node::Kind::Suffix:
            case Node::Kind::ThinFunctionType:
            case Node::Kind::TupleElement:
            case Node::Kind::TypeMangling:
            case Node::Kind::TypeMetadata:
            case Node::Kind::TypeMetadataAccessFunction:
            case Node::Kind::TypeMetadataLazyCache:
            case Node::Kind::UncurriedFunctionType:
            case Node::Kind::Unmanaged:
            case Node::Kind::Unowned:
            case Node::Kind::UnsafeAddressor:
            case Node::Kind::UnsafeMutableAddressor:
            case Node::Kind::ValueWitness:
            case Node::Kind::ValueWitnessTable:
            case Node::Kind::Variable:
            case Node::Kind::VTableAttribute:
            case Node::Kind::Weak:
            case Node::Kind::WillSet:
            case Node::Kind::WitnessTableOffset:
            case Node::Kind::ThrowsAnnotation:
                return false;
        }
        unreachable("bad node kind");
    }

    SugarType findSugar(NodePointer pointer) {
        if (pointer->getNumChildren() == 1 && pointer->getKind() == Node::Kind::Type)
            return findSugar(pointer->getChild(0));

        if (pointer->getNumChildren() != 2)
            return SugarType::None;

        if (pointer->getKind() != Node::Kind::BoundGenericEnum && pointer->getKind() != Node::Kind::BoundGenericStructure)
            return SugarType::None;

        auto unboundType = pointer->getChild(0)->getChild(0); // drill through Type
        auto typeArgs = pointer->getChild(1);

        if (pointer->getKind() == Node::Kind::BoundGenericEnum) {
            // Swift.Optional
            if (isIdentifier(unboundType->getChild(1), "Optional") && typeArgs->getNumChildren() == 1 && isSwiftModule(unboundType->getChild(0))) {
                return SugarType::Optional;
            }

            // Swift.ImplicitlyUnwrappedOptional
            if (isIdentifier(unboundType->getChild(1), "ImplicitlyUnwrappedOptional") && typeArgs->getNumChildren() == 1
                && isSwiftModule(unboundType->getChild(0))) {
                return SugarType::ImplicitlyUnwrappedOptional;
            }

            return SugarType::None;
        }

        assert(pointer->getKind() == Node::Kind::BoundGenericStructure);

        // Array
        if (isIdentifier(unboundType->getChild(1), "Array") && typeArgs->getNumChildren() == 1 && isSwiftModule(unboundType->getChild(0))) {
            return SugarType::Array;
        }

        // Dictionary
        if (isIdentifier(unboundType->getChild(1), "Dictionary") && typeArgs->getNumChildren() == 2 && isSwiftModule(unboundType->getChild(0))) {
            return SugarType::Dictionary;
        }

        return SugarType::None;
    }

    void printBoundGeneric(NodePointer pointer) {
        if (pointer->getNumChildren() < 2)
            return;
        if (pointer->getNumChildren() != 2) {
            printBoundGenericNoSugar(pointer);
            return;
        }

        if (!Options.SynthesizeSugarOnTypes || pointer->getKind() == Node::Kind::BoundGenericClass) {
            // no sugar here
            printBoundGenericNoSugar(pointer);
            return;
        }

        SugarType sugarType = findSugar(pointer);

        switch (sugarType) {
            case SugarType::None:
                printBoundGenericNoSugar(pointer);
                break;
            case SugarType::Optional:
            case SugarType::ImplicitlyUnwrappedOptional: {
                NodePointer type = pointer->getChild(1)->getChild(0);
                bool needs_parens = !isSimpleType(type);
                if (needs_parens)
                    Printer << "(";
                print(type);
                if (needs_parens)
                    Printer << ")";
                Printer << (sugarType == SugarType::Optional ? "?" : "!");
                break;
            }
            case SugarType::Array: {
                NodePointer type = pointer->getChild(1)->getChild(0);
                Printer << "[";
                print(type);
                Printer << "]";
                break;
            }
            case SugarType::Dictionary: {
                NodePointer keyType = pointer->getChild(1)->getChild(0);
                NodePointer valueType = pointer->getChild(1)->getChild(1);
                Printer << "[";
                print(keyType);
                Printer << " : ";
                print(valueType);
                Printer << "]";
                break;
            }
        }
    }

    void printSimplifiedEntityType(NodePointer context, NodePointer entityType);

    void printFunctionType(NodePointer node) {
        assert(node->getNumChildren() == 2 || node->getNumChildren() == 3);
        unsigned startIndex = 0;
        bool throws = false;
        if (node->getNumChildren() == 3) {
            assert(node->getChild(0)->getKind() == Node::Kind::ThrowsAnnotation);
            startIndex++;
            throws = true;
        }
        print(node->getChild(startIndex));
        if (throws)
            Printer << " throws";
        print(node->getChild(startIndex + 1));
    }

    void printImplFunctionType(NodePointer fn) {
        enum State { Attrs, Inputs, Results } curState = Attrs;
        auto transitionTo = [&](State newState) {
            assert(newState >= curState);
            for (; curState != newState; curState = State(curState + 1)) {
                switch (curState) {
                    case Attrs:
                        Printer << '(';
                        continue;
                    case Inputs:
                        Printer << ") -> (";
                        continue;
                    case Results:
                        unreachable("no state after Results");
                }
                unreachable("bad state");
            }
        };

        for (auto &child : *fn) {
            if (child->getKind() == Node::Kind::ImplParameter) {
                if (curState == Inputs)
                    Printer << ", ";
                transitionTo(Inputs);
                print(child);
            } else if (child->getKind() == Node::Kind::ImplResult || child->getKind() == Node::Kind::ImplErrorResult) {
                if (curState == Results)
                    Printer << ", ";
                transitionTo(Results);
                print(child);
            } else {
                assert(curState == Attrs);
                print(child);
                Printer << ' ';
            }
        }
        transitionTo(Results);
        Printer << ')';
    }

    void printContext(NodePointer context) {
        // TODO: parenthesize local contexts?
        if (Options.DisplayDebuggerGeneratedModule || !isDebuggerGeneratedModule(context)) {
            print(context, /*asContext*/ true);
            if (context->getKind() == Node::Kind::Module && !Options.DisplayModuleNames)
                return;
            Printer << '.';
        }
    }

    void print(NodePointer pointer, bool asContext = false, bool suppressType = false);

    unsigned printFunctionSigSpecializationParam(NodePointer pointer, unsigned Idx);
};
} // end anonymous namespace

static bool isExistentialType(NodePointer node) {
    assert(node->getKind() == Node::Kind::Type);
    node = node->getChild(0);
    return (node->getKind() == Node::Kind::ExistentialMetatype || node->getKind() == Node::Kind::ProtocolList);
}

/// Print the relevant parameters and return the new index.
unsigned NodePrinter::printFunctionSigSpecializationParam(NodePointer pointer, unsigned Idx) {
    NodePointer firstChild = pointer->getChild(Idx);
    unsigned V = (unsigned)firstChild->getIndex();
    auto K = FunctionSigSpecializationParamKind(V);
    switch (K) {
        case FunctionSigSpecializationParamKind::BoxToValue:
        case FunctionSigSpecializationParamKind::BoxToStack:
            print(pointer->getChild(Idx++));
            return Idx;
        case FunctionSigSpecializationParamKind::ConstantPropFunction:
        case FunctionSigSpecializationParamKind::ConstantPropGlobal: {
            Printer << "[";
            print(pointer->getChild(Idx++));
            Printer << " : ";
            const auto &text = pointer->getChild(Idx++)->getText();
            std::string demangledName = demangleSymbolAsString(text);
            if (demangledName.empty()) {
                Printer << text;
            } else {
                Printer << demangledName;
            }
            Printer << "]";
            return Idx;
        }
        case FunctionSigSpecializationParamKind::ConstantPropInteger:
        case FunctionSigSpecializationParamKind::ConstantPropFloat:
            Printer << "[";
            print(pointer->getChild(Idx++));
            Printer << " : ";
            print(pointer->getChild(Idx++));
            Printer << "]";
            return Idx;
        case FunctionSigSpecializationParamKind::ConstantPropString:
            Printer << "[";
            print(pointer->getChild(Idx++));
            Printer << " : ";
            print(pointer->getChild(Idx++));
            Printer << "'";
            print(pointer->getChild(Idx++));
            Printer << "'";
            Printer << "]";
            return Idx;
        case FunctionSigSpecializationParamKind::ClosureProp:
            Printer << "[";
            print(pointer->getChild(Idx++));
            Printer << " : ";
            print(pointer->getChild(Idx++));
            Printer << ", Argument Types : [";
            for (unsigned e = (unsigned)pointer->getNumChildren(); Idx < e;) {
                NodePointer child = pointer->getChild(Idx);
                // Until we no longer have a type node, keep demangling.
                if (child->getKind() != Node::Kind::Type)
                    break;
                print(child);
                ++Idx;

                // If we are not done, print the ", ".
                if (Idx < e && pointer->getChild(Idx)->hasText())
                    Printer << ", ";
            }
            Printer << "]";
            return Idx;
        default:
            break;
    }

    assert(((V & unsigned(FunctionSigSpecializationParamKind::OwnedToGuaranteed)) || (V & unsigned(FunctionSigSpecializationParamKind::SROA))
            || (V & unsigned(FunctionSigSpecializationParamKind::Dead)))
           && "Invalid OptionSet");
    print(pointer->getChild(Idx++));
    return Idx;
}

static bool isClassType(NodePointer pointer) {
    return pointer->getKind() == Node::Kind::Class;
}

static bool useColonForEntityType(NodePointer entity, NodePointer type) {
    switch (entity->getKind()) {
        case Node::Kind::Variable:
        case Node::Kind::Initializer:
        case Node::Kind::DefaultArgumentInitializer:
        case Node::Kind::IVarInitializer:
        case Node::Kind::Class:
        case Node::Kind::Structure:
        case Node::Kind::Enum:
        case Node::Kind::Protocol:
        case Node::Kind::TypeAlias:
        case Node::Kind::OwningAddressor:
        case Node::Kind::OwningMutableAddressor:
        case Node::Kind::NativeOwningAddressor:
        case Node::Kind::NativeOwningMutableAddressor:
        case Node::Kind::NativePinningAddressor:
        case Node::Kind::NativePinningMutableAddressor:
        case Node::Kind::UnsafeAddressor:
        case Node::Kind::UnsafeMutableAddressor:
        case Node::Kind::GlobalGetter:
        case Node::Kind::Getter:
        case Node::Kind::Setter:
        case Node::Kind::MaterializeForSet:
        case Node::Kind::WillSet:
        case Node::Kind::DidSet:
            return true;

        case Node::Kind::Subscript:
        case Node::Kind::Function:
        case Node::Kind::ExplicitClosure:
        case Node::Kind::ImplicitClosure:
        case Node::Kind::Allocator:
        case Node::Kind::Constructor:
        case Node::Kind::Destructor:
        case Node::Kind::Deallocator:
        case Node::Kind::IVarDestroyer: {
            // We expect to see a function type here, but if we don't, use the colon.
            type = type->getChild(0);
            while (type->getKind() == Node::Kind::DependentGenericType)
                type = type->getChild(1)->getChild(0);
            return (type->getKind() != Node::Kind::FunctionType && type->getKind() != Node::Kind::UncurriedFunctionType
                    && type->getKind() != Node::Kind::CFunctionPointer && type->getKind() != Node::Kind::ThinFunctionType);
        }

        default:
            unreachable("not an entity");
    }
}

static bool isMethodContext(const NodePointer &context) {
    switch (context->getKind()) {
        case Node::Kind::Structure:
        case Node::Kind::Enum:
        case Node::Kind::Class:
        case Node::Kind::Protocol:
        case Node::Kind::Extension:
            return true;
        default:
            return false;
    }
}

/// Perform any desired type simplifications for an entity in Simplified mode.
void NodePrinter::printSimplifiedEntityType(NodePointer context, NodePointer entityType) {
    // Only do anything special to methods.
    if (!isMethodContext(context))
        return print(entityType);

    // Strip off a single level of uncurried function type.
    NodePointer type = entityType;
    assert(type->getKind() == Node::Kind::Type);
    type = type->getChild(0);

    NodePointer generics;
    if (type->getKind() == Node::Kind::DependentGenericType) {
        generics = type->getChild(0);
        type = type->getChild(1)->getChild(0);
    }

    print(entityType);
}

void NodePrinter::print(NodePointer pointer, bool asContext, bool suppressType) {
    // Common code for handling entities.
    auto printEntity = [&](bool hasName, bool hasType, StringRef extraName) {
        if (Options.QualifyEntities)
            printContext(pointer->getChild(0));

        bool printType = (hasType && !suppressType);
        bool useParens = (printType && asContext);

        if (useParens)
            Printer << '(';

        if (hasName)
            print(pointer->getChild(1));
        Printer << extraName;

        if (printType) {
            NodePointer type = pointer->getChild(1 + unsigned(hasName));
            if (useColonForEntityType(pointer, type)) {
                if (Options.DisplayEntityTypes) {
                    Printer << " : ";
                    print(type);
                }
            } else if (!Options.DisplayEntityTypes) {
                printSimplifiedEntityType(pointer->getChild(0), type);
            } else {
                Printer << " ";
                print(type);
            }
        }

        if (useParens)
            Printer << ')';
    };

    Node::Kind kind = pointer->getKind();
    switch (kind) {
        case Node::Kind::Static:
            Printer << "static ";
            print(pointer->getChild(0), asContext, suppressType);
            return;
        case Node::Kind::Directness:
            Printer << toString(Directness(pointer->getIndex())) << " ";
            return;
        case Node::Kind::Extension:
            assert((pointer->getNumChildren() == 2 || pointer->getNumChildren() == 3) && "Extension expects 2 or 3 children.");
            if (Options.QualifyEntities && Options.DisplayExtensionContexts) {
                Printer << "(extension in ";
                // Print the module where extension is defined.
                print(pointer->getChild(0), true);
                Printer << "):";
            }
            print(pointer->getChild(1), asContext);
            if (pointer->getNumChildren() == 3)
                print(pointer->getChild(2), true);
            return;
        case Node::Kind::Variable:
        case Node::Kind::Function:
        case Node::Kind::Subscript:
            printEntity(true, true, "");
            return;
        case Node::Kind::ExplicitClosure:
        case Node::Kind::ImplicitClosure: {
            auto index = pointer->getChild(1)->getIndex();
            DemanglerPrinter printName;
            printName << '(';
            if (pointer->getKind() == Node::Kind::ImplicitClosure)
                printName << "implicit ";
            printName << "closure #" << (index + 1) << ")";
            printEntity(false, false, std::move(printName).str());
            return;
        }
        case Node::Kind::Global:
            printChildren(pointer);
            return;
        case Node::Kind::Suffix:
            if (!Options.DisplayUnmangledSuffix)
                return;
            Printer << " with unmangled suffix " << QuotedString(pointer->getText());
            return;
        case Node::Kind::Initializer:
            printEntity(false, false, "(variable initialization expression)");
            return;
        case Node::Kind::DefaultArgumentInitializer: {
            auto index = pointer->getChild(1);
            DemanglerPrinter strPrinter;
            strPrinter << "(default argument " << index->getIndex() << ")";
            printEntity(false, false, std::move(strPrinter).str());
            return;
        }
        case Node::Kind::DeclContext:
            print(pointer->getChild(0), asContext);
            return;
        case Node::Kind::Type:
            print(pointer->getChild(0), asContext);
            return;
        case Node::Kind::TypeMangling:
            print(pointer->getChild(0));
            return;
        case Node::Kind::Class:
        case Node::Kind::Structure:
        case Node::Kind::Enum:
        case Node::Kind::Protocol:
        case Node::Kind::TypeAlias:
            printEntity(true, false, "");
            return;
        case Node::Kind::LocalDeclName:
            Printer << '(';
            print(pointer->getChild(1));
            Printer << " #" << (pointer->getChild(0)->getIndex() + 1) << ')';
            return;
        case Node::Kind::PrivateDeclName:
            if (Options.ShowPrivateDiscriminators)
                Printer << '(';

            print(pointer->getChild(1));

            if (Options.ShowPrivateDiscriminators)
                Printer << " in " << pointer->getChild(0)->getText() << ')';
            return;
        case Node::Kind::Module:
            if (Options.DisplayModuleNames)
                Printer << pointer->getText();
            return;
        case Node::Kind::Identifier:
            Printer << pointer->getText();
            return;
        case Node::Kind::Index:
            Printer << pointer->getIndex();
            return;
        case Node::Kind::AutoClosureType:
            Printer << "@autoclosure ";
            printFunctionType(pointer);
            return;
        case Node::Kind::ThinFunctionType:
            Printer << "@convention(thin) ";
            printFunctionType(pointer);
            return;
        case Node::Kind::FunctionType:
        case Node::Kind::UncurriedFunctionType:
            printFunctionType(pointer);
            return;
        case Node::Kind::ArgumentTuple: {
            bool need_parens = false;
            if (pointer->getNumChildren() > 1)
                need_parens = true;
            else {
                if (!pointer->hasChildren())
                    need_parens = true;
                else {
                    Node::Kind child0_kind = pointer->getChild(0)->getChild(0)->getKind();
                    if (child0_kind != Node::Kind::VariadicTuple && child0_kind != Node::Kind::NonVariadicTuple)
                        need_parens = true;
                }
            }
            if (need_parens)
                Printer << "(";
            printChildren(pointer);
            if (need_parens)
                Printer << ")";
            return;
        }
        case Node::Kind::NonVariadicTuple:
        case Node::Kind::VariadicTuple: {
            Printer << "(";
            printChildren(pointer, ", ");
            if (pointer->getKind() == Node::Kind::VariadicTuple)
                Printer << "...";
            Printer << ")";
            return;
        }
        case Node::Kind::TupleElement:
            if (pointer->getNumChildren() == 1) {
                NodePointer type = pointer->getChild(0);
                print(type);
            } else if (pointer->getNumChildren() == 2) {
                NodePointer id = pointer->getChild(0);
                NodePointer type = pointer->getChild(1);
                print(id);
                print(type);
            }
            return;
        case Node::Kind::TupleElementName:
            Printer << pointer->getText() << " : ";
            return;
        case Node::Kind::ReturnType:
            if (pointer->getNumChildren() == 0)
                Printer << " -> " << pointer->getText();
            else {
                Printer << " -> ";
                printChildren(pointer);
            }
            return;
        case Node::Kind::Weak:
            Printer << "weak ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::Unowned:
            Printer << "unowned ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::Unmanaged:
            Printer << "unowned(unsafe) ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::InOut:
            Printer << "inout ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::NonObjCAttribute:
            Printer << "@nonobjc ";
            return;
        case Node::Kind::ObjCAttribute:
            Printer << "@objc ";
            return;
        case Node::Kind::DirectMethodReferenceAttribute:
            Printer << "super ";
            return;
        case Node::Kind::DynamicAttribute:
            Printer << "dynamic ";
            return;
        case Node::Kind::VTableAttribute:
            Printer << "override ";
            return;
        case Node::Kind::FunctionSignatureSpecialization:
        case Node::Kind::GenericSpecialization:
        case Node::Kind::GenericSpecializationNotReAbstracted: {
            if (!Options.DisplayGenericSpecializations) {
                Printer << "specialized ";
                return;
            }
            if (pointer->getKind() == Node::Kind::FunctionSignatureSpecialization) {
                Printer << "function signature specialization <";
            } else if (pointer->getKind() == Node::Kind::GenericSpecialization) {
                Printer << "generic specialization <";
            } else {
                Printer << "generic not re-abstracted specialization <";
            }
            bool hasPrevious = false;
            for (unsigned i = 0, e = (unsigned)pointer->getNumChildren(); i < e; ++i) {
                auto child = pointer->getChild(i);

                switch (pointer->getChild(i)->getKind()) {
                    case Node::Kind::SpecializationPassID:
                        // We skip the SpecializationPassID since it does not contain any
                        // information that is useful to our users.
                        continue;

                    case Node::Kind::SpecializationIsFragile:
                        break;

                    default:
                        // Ignore empty specializations.
                        if (!pointer->getChild(i)->hasChildren())
                            continue;
                }

                if (hasPrevious)
                    Printer << ", ";
                print(pointer->getChild(i));
                hasPrevious = true;
            }
            Printer << "> of ";
            return;
        }
        case Node::Kind::SpecializationIsFragile:
            Printer << "preserving fragile attribute";
            return;
        case Node::Kind::GenericSpecializationParam:
            print(pointer->getChild(0));
            for (unsigned i = 1, e = (unsigned)pointer->getNumChildren(); i < e; ++i) {
                if (i == 1)
                    Printer << " with ";
                else
                    Printer << " and ";
                print(pointer->getChild(i));
            }
            return;
        case Node::Kind::FunctionSignatureSpecializationParam: {
            uint64_t argNum = pointer->getIndex();

            Printer << "Arg[" << argNum << "] = ";

            unsigned Idx = printFunctionSigSpecializationParam(pointer, 0);

            for (unsigned e = (unsigned)pointer->getNumChildren(); Idx < e;) {
                Printer << " and ";
                Idx = printFunctionSigSpecializationParam(pointer, Idx);
            }

            return;
        }
        case Node::Kind::FunctionSignatureSpecializationParamPayload: {
            std::string demangledName = demangleSymbolAsString(pointer->getText());
            if (demangledName.empty()) {
                Printer << pointer->getText();
            } else {
                Printer << demangledName;
            }
            return;
        }
        case Node::Kind::FunctionSignatureSpecializationParamKind: {
            uint64_t raw = pointer->getIndex();

            bool printedOptionSet = false;
            if (raw & uint64_t(FunctionSigSpecializationParamKind::Dead)) {
                printedOptionSet = true;
                Printer << "Dead";
            }

            if (raw & uint64_t(FunctionSigSpecializationParamKind::OwnedToGuaranteed)) {
                if (printedOptionSet)
                    Printer << " and ";
                printedOptionSet = true;
                Printer << "Owned To Guaranteed";
            }

            if (raw & uint64_t(FunctionSigSpecializationParamKind::SROA)) {
                if (printedOptionSet)
                    Printer << " and ";
                Printer << "Exploded";
                return;
            }

            if (printedOptionSet)
                return;

            switch (FunctionSigSpecializationParamKind(raw)) {
                case FunctionSigSpecializationParamKind::BoxToValue:
                    Printer << "Value Promoted from Box";
                    break;
                case FunctionSigSpecializationParamKind::BoxToStack:
                    Printer << "Stack Promoted from Box";
                    break;
                case FunctionSigSpecializationParamKind::ConstantPropFunction:
                    Printer << "Constant Propagated Function";
                    break;
                case FunctionSigSpecializationParamKind::ConstantPropGlobal:
                    Printer << "Constant Propagated Global";
                    break;
                case FunctionSigSpecializationParamKind::ConstantPropInteger:
                    Printer << "Constant Propagated Integer";
                    break;
                case FunctionSigSpecializationParamKind::ConstantPropFloat:
                    Printer << "Constant Propagated Float";
                    break;
                case FunctionSigSpecializationParamKind::ConstantPropString:
                    Printer << "Constant Propagated String";
                    break;
                case FunctionSigSpecializationParamKind::ClosureProp:
                    Printer << "Closure Propagated";
                    break;
                case FunctionSigSpecializationParamKind::Dead:
                case FunctionSigSpecializationParamKind::OwnedToGuaranteed:
                case FunctionSigSpecializationParamKind::SROA:
                    unreachable("option sets should have been handled earlier");
            }
            return;
        }
        case Node::Kind::SpecializationPassID:
            Printer << pointer->getIndex();
            return;
        case Node::Kind::BuiltinTypeName:
            Printer << pointer->getText();
            return;
        case Node::Kind::Number:
            Printer << pointer->getIndex();
            return;
        case Node::Kind::InfixOperator:
            Printer << pointer->getText() << " infix";
            return;
        case Node::Kind::PrefixOperator:
            Printer << pointer->getText() << " prefix";
            return;
        case Node::Kind::PostfixOperator:
            Printer << pointer->getText() << " postfix";
            return;
        case Node::Kind::LazyProtocolWitnessTableAccessor:
            Printer << "lazy protocol witness table accessor for type ";
            print(pointer->getChild(0));
            Printer << " and conformance ";
            print(pointer->getChild(1));
            return;
        case Node::Kind::LazyProtocolWitnessTableCacheVariable:
            Printer << "lazy protocol witness table cache variable for type ";
            print(pointer->getChild(0));
            Printer << " and conformance ";
            print(pointer->getChild(1));
            return;
        case Node::Kind::ProtocolWitnessTableAccessor:
            Printer << "protocol witness table accessor for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::ProtocolWitnessTable:
            Printer << "protocol witness table for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::GenericProtocolWitnessTable:
            Printer << "generic protocol witness table for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::GenericProtocolWitnessTableInstantiationFunction:
            Printer << "instantiation function for generic protocol witness table for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::ProtocolWitness: {
            Printer << "protocol witness for ";
            print(pointer->getChild(1));
            Printer << " in conformance ";
            print(pointer->getChild(0));
            return;
        }
        case Node::Kind::PartialApplyForwarder:
            if (Options.ShortenPartialApply)
                Printer << "partial apply";
            else
                Printer << "partial apply forwarder";

            if (pointer->hasChildren()) {
                Printer << " for ";
                print(pointer->getFirstChild());
            }
            return;
        case Node::Kind::PartialApplyObjCForwarder:
            if (Options.ShortenPartialApply)
                Printer << "partial apply";
            else
                Printer << "partial apply ObjC forwarder";

            if (pointer->hasChildren()) {
                Printer << " for ";
                print(pointer->getFirstChild());
            }
            return;
        case Node::Kind::FieldOffset: {
            print(pointer->getChild(0)); // directness
            Printer << "field offset for ";
            auto entity = pointer->getChild(1);
            print(entity,
                  /*asContext*/ false,
                  /*suppressType*/ !Options.DisplayTypeOfIVarFieldOffset);
            return;
        }
        case Node::Kind::ReabstractionThunk:
        case Node::Kind::ReabstractionThunkHelper: {
            if (Options.ShortenThunk) {
                Printer << "thunk";
                return;
            }
            Printer << "reabstraction thunk ";
            if (pointer->getKind() == Node::Kind::ReabstractionThunkHelper)
                Printer << "helper ";
            auto generics = getFirstChildOfKind(pointer, Node::Kind::DependentGenericSignature);
            assert(pointer->getNumChildren() == 2 + unsigned(generics != nullptr));
            if (generics) {
                print(generics);
                Printer << " ";
            }
            Printer << "from ";
            print(pointer->getChild(pointer->getNumChildren() - 2));
            Printer << " to ";
            print(pointer->getChild(pointer->getNumChildren() - 1));
            return;
        }
        case Node::Kind::GenericTypeMetadataPattern:
            Printer << "generic type metadata pattern for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::Metaclass:
            Printer << "metaclass for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::ProtocolDescriptor:
            Printer << "protocol descriptor for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::FullTypeMetadata:
            Printer << "full type metadata for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::TypeMetadata:
            Printer << "type metadata for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::TypeMetadataAccessFunction:
            Printer << "type metadata accessor for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::TypeMetadataLazyCache:
            Printer << "lazy cache variable for type metadata for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::AssociatedTypeMetadataAccessor:
            Printer << "associated type metadata accessor for ";
            print(pointer->getChild(1));
            Printer << " in ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::AssociatedTypeWitnessTableAccessor:
            Printer << "associated type witness table accessor for ";
            print(pointer->getChild(1));
            Printer << " : ";
            print(pointer->getChild(2));
            Printer << " in ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::NominalTypeDescriptor:
            Printer << "nominal type descriptor for ";
            print(pointer->getChild(0));
            return;
        case Node::Kind::ValueWitness:
            Printer << toString(ValueWitnessKind(pointer->getIndex()));
            if (Options.ShortenValueWitness)
                Printer << " for ";
            else
                Printer << " value witness for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::ValueWitnessTable:
            Printer << "value witness table for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::WitnessTableOffset:
            Printer << "witness table offset for ";
            print(pointer->getFirstChild());
            return;
        case Node::Kind::BoundGenericClass:
        case Node::Kind::BoundGenericStructure:
        case Node::Kind::BoundGenericEnum:
            printBoundGeneric(pointer);
            return;
        case Node::Kind::DynamicSelf:
            Printer << "Self";
            return;
        case Node::Kind::CFunctionPointer: {
            Printer << "@convention(c) ";
            printFunctionType(pointer);
            return;
        }
        case Node::Kind::ObjCBlock: {
            Printer << "@convention(block) ";
            printFunctionType(pointer);
            return;
        }
        case Node::Kind::SILBoxType: {
            Printer << "@box ";
            NodePointer type = pointer->getChild(0);
            print(type);
            return;
        }
        case Node::Kind::Metatype: {
            unsigned Idx = 0;
            if (pointer->getNumChildren() == 2) {
                NodePointer repr = pointer->getChild(Idx);
                print(repr);
                Printer << " ";
                Idx++;
            }
            NodePointer type = pointer->getChild(Idx);
            print(type);
            if (isExistentialType(type)) {
                Printer << ".Protocol";
            } else {
                Printer << ".Type";
            }
            return;
        }
        case Node::Kind::ExistentialMetatype: {
            unsigned Idx = 0;
            if (pointer->getNumChildren() == 2) {
                NodePointer repr = pointer->getChild(Idx);
                print(repr);
                Printer << " ";
                Idx++;
            }

            NodePointer type = pointer->getChild(Idx);
            print(type);
            Printer << ".Type";
            return;
        }
        case Node::Kind::MetatypeRepresentation: {
            Printer << pointer->getText();
            return;
        }
        case Node::Kind::ArchetypeRef:
            Printer << pointer->getText();
            return;
        case Node::Kind::AssociatedTypeRef:
            print(pointer->getChild(0));
            Printer << '.' << pointer->getChild(1)->getText();
            return;
        case Node::Kind::SelfTypeRef:
            print(pointer->getChild(0));
            Printer << ".Self";
            return;
        case Node::Kind::ProtocolList: {
            NodePointer type_list = pointer->getChild(0);
            if (!type_list)
                return;
            if (type_list->getNumChildren() == 0)
                Printer << "Any";
            else
                printChildren(type_list, " & ");
            return;
        }
        case Node::Kind::Archetype: {
            Printer << pointer->getText();
            if (pointer->hasChildren()) {
                Printer << " : ";
                print(pointer->getChild(0));
            }
            return;
        }
        case Node::Kind::AssociatedType:
            // Don't print for now.
            return;
        case Node::Kind::QualifiedArchetype: {
            if (Options.ShortenArchetype) {
                Printer << "(archetype)";
                return;
            }
            if (pointer->getNumChildren() < 2)
                return;
            NodePointer number = pointer->getChild(0);
            NodePointer decl_ctx = pointer->getChild(1);
            Printer << "(archetype " << number->getIndex() << " of ";
            print(decl_ctx);
            Printer << ")";
            return;
        }
        case Node::Kind::OwningAddressor:
            printEntity(true, true, ".owningAddressor");
            return;
        case Node::Kind::OwningMutableAddressor:
            printEntity(true, true, ".owningMutableAddressor");
            return;
        case Node::Kind::NativeOwningAddressor:
            printEntity(true, true, ".nativeOwningAddressor");
            return;
        case Node::Kind::NativeOwningMutableAddressor:
            printEntity(true, true, ".nativeOwningMutableAddressor");
            return;
        case Node::Kind::NativePinningAddressor:
            printEntity(true, true, ".nativePinningAddressor");
            return;
        case Node::Kind::NativePinningMutableAddressor:
            printEntity(true, true, ".nativePinningMutableAddressor");
            return;
        case Node::Kind::UnsafeAddressor:
            printEntity(true, true, ".unsafeAddressor");
            return;
        case Node::Kind::UnsafeMutableAddressor:
            printEntity(true, true, ".unsafeMutableAddressor");
            return;
        case Node::Kind::GlobalGetter:
            printEntity(true, true, ".getter");
            return;
        case Node::Kind::Getter:
            printEntity(true, true, ".getter");
            return;
        case Node::Kind::Setter:
            printEntity(true, true, ".setter");
            return;
        case Node::Kind::MaterializeForSet:
            printEntity(true, true, ".materializeForSet");
            return;
        case Node::Kind::WillSet:
            printEntity(true, true, ".willset");
            return;
        case Node::Kind::DidSet:
            printEntity(true, true, ".didset");
            return;
        case Node::Kind::Allocator:
            printEntity(false, true, isClassType(pointer->getChild(0)) ? "__allocating_init" : "init");
            return;
        case Node::Kind::Constructor:
            printEntity(false, true, "init");
            return;
        case Node::Kind::Destructor:
            printEntity(false, false, "deinit");
            return;
        case Node::Kind::Deallocator:
            printEntity(false, false, isClassType(pointer->getChild(0)) ? "__deallocating_deinit" : "deinit");
            return;
        case Node::Kind::IVarInitializer:
            printEntity(false, false, "__ivar_initializer");
            return;
        case Node::Kind::IVarDestroyer:
            printEntity(false, false, "__ivar_destroyer");
            return;
        case Node::Kind::ProtocolConformance: {
            NodePointer child0 = pointer->getChild(0);
            NodePointer child1 = pointer->getChild(1);
            NodePointer child2 = pointer->getChild(2);
            print(child0);
            if (Options.DisplayProtocolConformances) {
                Printer << " : ";
                print(child1);
                Printer << " in ";
                print(child2);
            }
            return;
        }
        case Node::Kind::TypeList:
            printChildren(pointer);
            return;
        case Node::Kind::ImplConvention:
            Printer << pointer->getText();
            return;
        case Node::Kind::ImplFunctionAttribute:
            Printer << pointer->getText();
            return;
        case Node::Kind::ImplErrorResult:
            Printer << "@error ";
            SWIFT_FALLTHROUGH;
        case Node::Kind::ImplParameter:
        case Node::Kind::ImplResult:
            printChildren(pointer, " ");
            return;
        case Node::Kind::ImplFunctionType:
            printImplFunctionType(pointer);
            return;
        case Node::Kind::ErrorType:
            Printer << "<ERROR TYPE>";
            return;

        case Node::Kind::DependentPseudogenericSignature:
        case Node::Kind::DependentGenericSignature: {
            Printer << '<';

            unsigned depth = 0;
            unsigned numChildren = (unsigned)pointer->getNumChildren();
            for (; depth < numChildren && pointer->getChild(depth)->getKind() == Node::Kind::DependentGenericParamCount; ++depth) {
                if (depth != 0)
                    Printer << "><";

                unsigned count = (unsigned)pointer->getChild(depth)->getIndex();
                for (unsigned index = 0; index < count; ++index) {
                    if (index != 0)
                        Printer << ", ";
                    // FIXME: Depth won't match when a generic signature applies to a
                    // method in generic type context.
                    Printer << archetypeName(index, depth);
                }
            }

            if (depth != numChildren) {
                if (!Options.DisplayWhereClauses) {
                    Printer << " where ...";
                } else {
                    Printer << " where ";
                    for (unsigned i = depth; i < numChildren; ++i) {
                        if (i > depth)
                            Printer << ", ";
                        print(pointer->getChild(i));
                    }
                }
            }
            Printer << '>';
            return;
        }
        case Node::Kind::DependentGenericParamCount:
            unreachable("should be printed as a child of a "
                        "DependentGenericSignature");
        case Node::Kind::DependentGenericConformanceRequirement: {
            NodePointer type = pointer->getChild(0);
            NodePointer reqt = pointer->getChild(1);
            print(type);
            Printer << ": ";
            print(reqt);
            return;
        }
        case Node::Kind::DependentGenericSameTypeRequirement: {
            NodePointer fst = pointer->getChild(0);
            NodePointer snd = pointer->getChild(1);

            print(fst);
            Printer << " == ";
            print(snd);
            return;
        }
        case Node::Kind::DependentGenericParamType: {
            Printer << pointer->getText();
            return;
        }
        case Node::Kind::DependentGenericType: {
            NodePointer sig = pointer->getChild(0);
            NodePointer depTy = pointer->getChild(1);
            print(sig);
            Printer << ' ';
            print(depTy);
            return;
        }
        case Node::Kind::DependentMemberType: {
            NodePointer base = pointer->getChild(0);
            print(base);
            Printer << '.';
            NodePointer assocTy = pointer->getChild(1);
            print(assocTy);
            return;
        }
        case Node::Kind::DependentAssociatedTypeRef: {
            Printer << pointer->getText();
            return;
        }
        case Node::Kind::ThrowsAnnotation: {
            Printer << " throws ";
            return;
        }
    }
    unreachable("bad node kind!");
}

std::string Demangle::nodeToString(NodePointer root, const DemangleOptions &options) {
    if (!root)
        return "";

    return NodePrinter(options).printRoot(root);
}

std::string Demangle::demangleSymbolAsString(const char *MangledName, size_t MangledNameLength, const DemangleOptions &Options) {
    auto mangled = StringRef(MangledName, MangledNameLength);
    auto root = demangleSymbolAsNode(MangledName, MangledNameLength, Options);
    if (!root)
        return mangled.str();

    std::string demangling = nodeToString(std::move(root), Options);
    if (demangling.empty())
        return mangled.str();
    return demangling;
}

std::string Demangle::demangleTypeAsString(const char *MangledName, size_t MangledNameLength, const DemangleOptions &Options) {
    auto mangled = StringRef(MangledName, MangledNameLength);
    auto root = demangleTypeAsNode(MangledName, MangledNameLength, Options);
    if (!root)
        return mangled.str();

    std::string demangling = nodeToString(std::move(root), Options);
    if (demangling.empty())
        return mangled.str();
    return demangling;
}
